Greedy algorithms
Introduzido
Vocabulário
| English | Significado |
|---|---|
| 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}
Prática
The exchange argument shows —
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
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}
Prática
Earliest-finish on the course activities picks —
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
(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}
Prática
Coins 1, 3, 4 for target 6: greedy pays — coins
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Greedy takes 4+1+1 = three coins; the DP optimum is 3+3 = two.