Unit 5: Dynamic Programming
In this unit, we will study another popular computer science algorithmic paradigm called the dynamic programming. Dynamic programming, like the divide-and-conquer method, solves problem by combining solutions to sub-problems. Dynamic programming typically applies to optimization problems in which a set of choices must be made in order to arrive at an optimal solution. It is effective when a given sub-problem may arise from more than one partial set of choices. We will look into problems, such as the longest common subsequence and the knapsack problem, to explain the key ideas behind dynamic programming.
Completing this unit should take you approximately 7 hours.
5.1: Introduction to Dynamic Programming
Read Chapter 6 of S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani's book Algorithms.
5.2: Dynamic Programming
Watch this video to learn about dynamic programming concepts.
5.3: The Knapsack Problem
Watch this video series to learn about how the knapsack problem is solved using dynamic programming techniques.
5.4: Dynamic Programming Examples
Read this article to learn about the different types of problems to which dynamic programming techniques are applied.
Complete all questions in this activity. There is one question on the dynamic-programming paradigm that requires two implementations. The first one involves the use of the regular approach to matrix multiplication, and the second one requires the dynamic programming approach. You have to compare the runtimes for the two approaches. You can check your answers against the Answer Key.