What are effective approaches for teaching dynamic programming?

Question

Dynamic programming is a subject that's notoriously difficult to learn and to teach. It's one thing to educate oneself, say by reading the appropriate chapters in Kleinberg & Tardos or CLRS, and working through a sufficient number of example problems. It's another matter to learn or teach this material in a classroom setting at the high school, undergraduate, or graduate level. Intrinsic to the subject is the skill of identifying the type of problem structure that's amenable to the dynamic programming approach.

In light of this, what are effective approaches for teaching dynamic programming?

Answer 1

I think it's really about breaking down the concepts into smaller pieces. First a student needs to understand recursion well, then they can understand memoization and dynamic programming. It's hard to just jump into e.g. the knapsack problem without first having worked through simpler problems. After one gets practice with the basic concepts, dynamic programming isn't inherently so difficult. Here's a basic way one can break it down:

• Recursion
  • As an alternative to loops
  • Binary search
  • Divide and conquer
  • Backtracking
• Memoization
  • Backtracking can be inefficient. Why not cache the results as you go through them?
  • Simple problems, such as reaching a specific sum with certain coins.
  • Can then consider harder problems, where a 2D array is required.
• Dynamic programming (DP)
  • Consider the coin sum problem again. How would one be solve it manually for the numbers 1 - 10? Can this "build-up" solution be put into code?
  • Solving more advanced problems with dynamic programming instead of recursion/memoization.
  • Identifying problems for DP approaches - Partially this comes with experience of solving a few different problems. But there's a standard pattern one can recognize - if a recursive solution can be used to get a solution very inefficiently (by repeatedly searching through the same subproblems), then memoization and DP can be used to make it more efficient.

(If you're interested, I also created a free tutorial on Recursion that breaks it down as above with programming challenges.)

Answer 2

I have a contrary view. Dynamic programming and it's close cousin memoization are actually pretty easy to teach. It's true that students frequently struggle mightily with dynamic programming, but I strongly believe that it's usually not the actual dynamic programming that they're struggling with, but rather the underlying recursive relationships. If I help them review recursion and give them lots (and lots and lots) of practice coming up with the kinds of brute-force recursive algorithms that dynamic programming replaces, then taking the extra step to dynamic programming is relatively straightforward.

I think dynamic programming is a perfect example where skill B depends on skill A, and we mis-attribute student weakness with B, when the real weakness is with skill A instead.

Answer 3

I will draw on my experience as a student of two online courses that have attempted to teach this topic. The first is the MITx course 6.00.2x Introduction to Computational Thinking and Data Science. The sections of the first unit are (1) optimization and the knapsack problem; (2) decision trees and dynamic programming; and (3) graph problems.

Using optimization and decision trees as lead-ins to dynamic programming made it clear why the approach has value. The decision trees gave a good visual aid that still sticks with me. The course also uses the (somewhat cliché) Fibonacci example to show how memoization drastically speeds up the algorithm, and makes it computationally reasonable for numbers beyond the mid-30s. Here is the YouTube link to the lecture: MITx on Dynamic Programming.

I also recommend looking into UW's Coursera offering Programming Languages, Part B. It focuses on Racket, and its section on memoization mentions dynamic programming in passing. Here are the lecture notes (relevant section starts on p. 15) and video for its materials: Programming Languages on memoization and the corresponding lecture video.