Stage 1 · Code
Greedy Algorithms
Greedy Proofs
Exchange argument, greedy stays ahead, and matroid theory.
Exchange Argument
The exchange argument proves greedy optimality by showing that any optimal solution can be transformed into the greedy solution without worsening it. Swap greedy choice with optimal choice and show it's still valid.
Greedy Stays Ahead
Greedy stays ahead shows that after each step, the greedy solution is at least as good as any other solution up to that point. Maintain an invariant that greedy never falls behind.
Matroid Theory
A matroid is a structure that generalizes linear independence. Greedy algorithms are optimal for matroids. A matroid has: (1) ground set E, (2) family I of independent sets satisfying hereditary and exchange properties.
When Greedy Fails
Greedy fails when local optimal choices don't lead to global optimum. Common failure modes: (1) Future choices depend on current choice in complex ways, (2) Need to backtrack, (3) Problem requires considering trade-offs.
| Problem | Greedy Works? | Reason |
|---|---|---|
| Activity selection | Yes | Earliest finish optimal |
| Fractional knapsack | Yes | Take highest value/weight |
| 0/1 knapsack | No | Fractional assumption fails |
| Minimum spanning tree | Yes | Cut property |
| Shortest path (DAG) | Yes | Topological order |
| Longest path | No | No optimal substructure |
| Coin change (canonical) | Sometimes | Depends on coin system |
Before implementing a greedy algorithm, sketch a proof. If you can't prove it works, consider dynamic programming or other approaches. Many interview problems are designed to make greedy fail.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.