Greedy algorithms
Introduit
Vocabulaire
| English | Sens |
|---|---|
| greedy algorithm | greedy algorithm |
| exchange argument | exchange argument |
English
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}
Pratique
The exchange argument shows —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Swap optimal picks for greedy ones losslessly: same size, still feasible.
English
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}
Pratique
Earliest-finish on the course activities picks —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
(1,4), (5,7), (8,11), (12,16) - four, provably optimal.
English
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}
Pratique
Coins 1, 3, 4 for target 6: greedy pays — coins
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Greedy takes 4+1+1 = three coins; the DP optimum is 3+3 = two.