### 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.**

Upon successful completion of this unit, you will be able to:

- Describe the dynamic programming technique for solving a class of problems.

### 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.