Unit 12: Dynamic Programming

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 (preliminary)

---

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