Greedy Algorithms
The problem
Some optimization problems can be solved by always making the choice that looks best right now, never reconsidering it later — when this works, it's dramatically simpler and faster than exploring every possibility, but using it on a problem where it doesn't actually hold produces a confidently wrong answer.
Why now
Dynamic programming already showed one way to handle problems with optimal substructure — by exploring and caching every relevant subproblem. Greedy algorithms are the much cheaper alternative that works only when a stronger condition holds: proof techniques already gave the exchange-argument style of reasoning needed to actually justify that a locally-best choice never needs revisiting.
Mental model
A greedy algorithm makes the locally optimal choice at every step and never looks back — cheap, but only correct if the problem has the 'greedy choice property': committing to the best immediate option never rules out reaching the globally best solution. Proving that property usually takes an exchange argument — show that any optimal solution can be rearranged to include the greedy choice without getting worse, which is exactly the kind of argument proof-techniques already trained.
Requires
- Complexity Analysis in PracticeComputer Science Fundamentals
Greedy algorithms are usually presented and chosen specifically because they're cheaper than the dynamic-programming or brute-force alternative; you need the ability to compare those costs already in hand to appreciate what a correct greedy algorithm buys you.
- Proof TechniquesMathematical Thinking
A greedy algorithm's correctness is never obvious from the algorithm alone — it requires an exchange-argument proof that the greedy choice property actually holds, which is a direct, non-optional application of the proof techniques already covered.
Used in
- Huffman coding for optimal data compression
- Activity/interval scheduling to maximize the number of non-overlapping events
- Kruskal's and Prim's minimum spanning tree algorithms
- Coin-change problems, where greedy works for some coin systems and provably fails for others
Projects
- Solve the activity-selection problem (maximize non-overlapping intervals) greedily, then write out the exchange-argument proof for why choosing the earliest-finishing activity first is always safe
- Find a coin denomination system where the standard greedy 'always pick the largest coin' approach fails to produce the minimum number of coins, and explain why
Examples
- US coin denominations (25, 10, 5, 1) happen to make greedy coin-change always optimal; an arbitrary denomination set like (1, 3, 4) can make greedy give a suboptimal answer for a target like 6
- Interval scheduling's greedy rule — always pick the activity that finishes earliest — is provably optimal via an exchange argument, not just empirically observed to work
Resources
Mastery checklist
- I can implement a greedy solution to a classic problem like activity selection
- I can write or follow an exchange-argument proof of a greedy algorithm's correctness
- I can construct a counterexample showing when a plausible-looking greedy strategy fails
- I can decide whether a new optimization problem is a legitimate candidate for a greedy approach