Reading¶
-
Dasgupta, Papadimitriou, and Vazirani: 6 - Dynamic Programming [PDF]
- 0-1 Knapsack is Section 6.4, Floyd/Warshall is 6.6.
-
Jeff Erickson’s Chapter 3 - Dynamic Programming
- Very well-presented, though it doesn’t cover the specific algorithms we’ll look at in class.
Supplemental¶
-
DS&AA:
Section 16.1
- Covers dynamic programming generally, including a variant of the Knapsack Problem.
Levitin¶
- Levitin 8.0-8.1
- Dynamic Programming
- Levitin 8.2
- 0-1 Knapsack Problem
- Levitin 8.4
- Transitive Closure; Floyd/Warshall Algorithm