Greedy Algorithms and Correctness Proofs

Dijkstra's algorithm and Kruskal/Prim both made an irrevocable local choice at every step — "take the cheapest thing available right now" — and never looked back. This is a greedy algorithm, and this lesson names the pattern and its two proof obligations explicitly: the greedy-choice property (a locally optimal choice is always part of some globally optimal solution) and optimal substructure (an optimal solution to the whole problem contains optimal solutions to its subproblems). Both are illustrated on interval scheduling and Huffman coding, two of the cleanest worked greedy correctness proofs in the CLRS canon.