main page — CS 566 Efficient Algorithms
Unit 12: Dynamic Programming
This is an archived version of this module from Winter 2025-26.
Click here for the current iteration.
This unit covers the algorithm design technique dynamic programming. Specifically, we will cover the common steps in designing dynamic programming algorithms, and we will discuss a number of examples, including
- matrix-chain multiplication,
- making change,
- the Bellman-Ford algorithm,
- optimal binary search trees,
- edit distance.
Learning outcomes
- Be able to apply the DP paradigm to solve new problems.
Material
- slides
- Video 12-1 (2025-01-21, 16:22):
§12.1 Introduction
(last year’s video due to snow storm)
- Video 12-2 (2025-01-27, 55:45):
§12.2 Matrix-Chain Multiplication
(last year’s video due to snow storm)
- Video 12-3 (2025-01-27, 6:57):
§12.3 Greedy as DP
(last year’s video due to snow storm)
- Video 12-4 (2025-01-27, 21:12):
§12.4 Bellman-Ford
(last year’s video due to snow storm)
- Video 12-5 (2026-01-27, 8:28):
§12.4 Bellman-Ford implementation
- Video 12-6 (2026-01-27, 18:14):
§12.5 Change-making by DP
- Video 12-7 (2026-01-27, 17:35):
§12.6 Optimal binary search trees
- Video 12-8 (2026-01-27, 19:32):
§12.7 Edit distance
Further reading and sources
The presentation of dynamic programming follows
and takes inspiration from