Greedy algorithms
Introduced
Vocabulary
| English | Meaning |
|---|---|
| greedy algorithm | An algorithm making a locally preferred choice at each step without revisiting earlier choices. |
| exchange argument | A proof showing that choices in an optimal solution can be replaced by proposed choices without worsening it. |
Take the best now
- A greedy algorithm builds the solution piece by piece, always taking the locally best piece. Correctness is a proof, not a hope: exchange arguments show any optimal solution can be transformed into the greedy one without loss.
{exercise:uni-cs1003-greedy}
Practice
The exchange argument shows —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Swap optimal picks for greedy ones losslessly: same size, still feasible.
Activity selection, measured
- Course activities: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16). Earliest-finish picks (1,4), (5,7), (8,11), (12,16) — four, provably optimal.
- The exchange argument once: finish($G_1$) $\le$ finish($O_1$), so swapping the optimal's first pick for the greedy's keeps feasibility — repeat, and optimal becomes greedy, unchanged in size.
{exercise:uni-cs1003-activity}
Practice
Earliest-finish on the course activities picks —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
(1,4), (5,7), (8,11), (12,16) - four, provably optimal.
Where greedy fails, and Huffman where it wins
- Coins 1, 3, 4, target 6: greedy pays 4+1+1 (three coins); the DP table pays 3+3 (two). The exchange argument fails, so greedy is a heuristic there.
- Huffman on frequencies 5, 9, 12, 13, 16, 45: repeatedly merge the two smallest — weighted depth 224 bits against 300 for a fixed-length code: provably minimal by the leaf-swap argument.
{exercise:uni-cs1003-huffman}
Practice
Coins 1, 3, 4 for target 6: greedy pays — coins
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Greedy takes 4+1+1 = three coins; the DP optimum is 3+3 = two.