Answers.Body: <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-06T21:46:18.743Z
Answers.LastActivityDate: 2017-06-06T21:46:18.743Z
Answers.UserDisplayName: Chris Okasaki
Answers.Body: <p>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:</p>
  
  <ul>
  <li>Recursion
  
  <ul>
  <li>As an alternative to loops</li>
  <li>Binary search</li>
  <li>Divide and conquer</li>
  <li>Backtracking</li>
  </ul></li>
  <li>Memoization
  
  <ul>
  <li>Backtracking can be inefficient. Why not cache the results as you go through them?</li>
  <li>Simple problems, such as reaching a specific sum with certain coins.</li>
  <li>Can then consider harder problems, where a 2D array is required.</li>
  </ul></li>
  <li>Dynamic programming (DP)
  
  <ul>
  <li>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?</li>
  <li>Solving more advanced problems with dynamic programming instead of recursion/memoization.</li>
  <li>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. </li>
  </ul></li>
  </ul>
  
  <p>(If you're interested, I also created a free <a href="https://www.learneroo.com/modules/71/nodes/398" rel="nofollow noreferrer">tutorial on Recursion</a> that breaks it down as above with programming challenges.)</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-06-14T12:51:21.757Z
Answers.LastActivityDate: 2017-06-18T11:26:02.353Z
Answers.LastEditDate: 2017-06-18T11:26:02.353Z
Answers.UserDisplayName: Ari
Answers.Body: <p>I will draw on my experience as a student of two online courses that have attempted to teach this topic. The first is the <strong>MITx course 6.00.2x</strong> <em>Introduction to Computational Thinking and Data Science</em>. The sections of the first unit are (1) optimization and the knapsack problem; (2) decision trees and dynamic programming; and (3) graph problems.</p>
  
  <p>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: <a href="https://www.youtube.com/watch?v=_3B_WuCRjtg" rel="nofollow noreferrer">MITx on Dynamic Programming</a>.</p>
  
  <p>I also recommend looking into <a href="https://www.coursera.org/learn/programming-languages-part-b" rel="nofollow noreferrer">UW's Coursera offering Programming Languages, Part B</a>. 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: <a href="http://courses.cs.washington.edu/courses/cse341/17sp/unit5notes.pdf" rel="nofollow noreferrer">Programming Languages on memoization</a> and the corresponding <a href="http://courses.cs.washington.edu/courses/cse341/13wi/videos/unit5/100_memoization.mp4" rel="nofollow noreferrer">lecture video</a>.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-05-24T23:28:33.543Z
Answers.LastActivityDate: 2017-05-25T12:27:29.973Z
Answers.LastEditDate: 2017-05-25T12:27:29.973Z
Answers.UserDisplayName: Peter
Body: <p>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 &amp; 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.</p>
  
  <p>In light of this, what are effective approaches for teaching dynamic programming?</p>
  
Tags: <lesson-ideas><algorithms>
Title: What are effective approaches for teaching dynamic programming?
ThreadText: # What are effective approaches for teaching dynamic programming?
  
  (Asked by: username_0 on 2017-05-23)
  
  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?
  
  **Tags:** lesson-ideas, algorithms
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2017-06-14. Score: 8
  
  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](https://www.learneroo.com/modules/71/nodes/398) that breaks it down as above with programming challenges.)
  
  
  ---
  
  ### Answer by username_1 on 2017-06-06. Score: 5
  
  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 by username_3 on 2017-05-24. Score: 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](https://www.youtube.com/watch?v=_3B_WuCRjtg).
  
  I also recommend looking into [UW's Coursera offering Programming Languages, Part B](https://www.coursera.org/learn/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](http://courses.cs.washington.edu/courses/cse341/17sp/unit5notes.pdf) and the corresponding [lecture video](http://courses.cs.washington.edu/courses/cse341/13wi/videos/unit5/100_memoization.mp4).
  
  
  ---
  
  