Unit 12: Dynamic Programming

This is an archived version of this module from Winter 2024-25.
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

1. Be able to apply the DP paradigm to solve new problems.

Material

• slides

• lecture notes

• Video 12-1 (2025-01-21): §12.1 Introduction

• Video 12-2 (2025-01-27): §12.2 Matrix-Chain Multiplication

• Video 12-3 (2025-01-27): §12.3 Greedy as DP

• Video 12-4 (2025-01-27): §12.4 Bellman-Ford

• Video 12-5 (2025-01-28): §12.4 Bellman-Ford implementation

• Video 12-6 (2025-01-28): §12.5 Change-making by DP

• Video 12-7 (2025-01-28): §12.6 Optimal binary search trees

• Video 12-8 (2025-01-28): §12.7 Edit distance

---

Further reading and sources

The presentation of dynamic programming follows

• Nebel, Wild: Entwurf und Analyse von Algorithmen (2018), Springer Vieweg

and takes inspiration from

• Demaine, Devadas: 6.006 Introduction to Algorithms (2011), MIT OpenCourseWare

---

Unit 11  ⋅  Syllabus  ⋅  Unit 13