Overview

Every algorithm this unit has built so far — mergesort, quicksort, Dijkstra, Kruskal, Union-Find — is a specific instance of a small number of reusable design templates, and this topic names them explicitly: divide-and-conquer (already used, revisited here as a named pattern), greedy algorithms (with the exchange-argument proof technique generalised from Dijkstra's and Kruskal/Prim's correctness proofs), and dynamic programming (the recipe behind Floyd-Warshall, named and generalised as SRBOT). Recognising which paradigm a new problem fits is the single highest-leverage skill this whole unit has been building toward — most of algorithm design in practice is pattern-matching a new problem against this small toolkit, not inventing something genuinely new.