An Elementary Approach Towards Teaching Dynamic Programming

Abstract

Dynamic programming has its firm place in the toolbox of a computer scientist. Its educational value, however, goes far beyond the border of our discipline. The example of dynamic programming illustrates how such an important algorithm design principle, and more generally algorithmic thinking skills, can be applied to solve problems in other fields. We describe our experiences with an approach towards teaching dynamic programming without a formal introduction to recursion, which allowed us to successfully introduce it to first-semester students of natural sciences with almost no background in computer science.