Unit 12: Dynamic Programming

This is an archived version of this module from Winter 2024-25.

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