Greedy Algorithms as a Design Strategy
Pseudocode & Algorithmic Problem-Solving
Chapter 7 · Greedy Algorithms as a Design Strategy
A greedy algorithm makes the choice that looks best right now, at every step, and never revisits or reconsiders it. It's fast and simple to write — and whether it's actually correct depends entirely on the problem's own structure. This chapter runs the exact same greedy algorithm on two different inputs: one where it provably matches the true optimum, and one where it provably doesn't.
The Algorithm: Greedy Coin Change
At every step, it grabs the largest coin that still fits — the locally optimal choice — and never looks back.
Case 1: Greedy Matches the True Optimum
Run on standard US coin denominations (25, 10, 5, 1), and cross-checked against a true optimum computed independently (via dynamic programming — trying every combination systematically, not greedily):
amount=41: greedy gives [25,10,5,1], 4 coins — the independently-computed true optimum is also 4 coins. amount=63: greedy gives [25,25,10,1,1,1], 6 coins — true optimum is also 6. amount=99: greedy gives [25,25,25,10,10,1,1,1,1], 9 coins — true optimum is also 9. Three separate amounts, greedy's result matches an independently-verified optimum every time.
Case 2: The Exact Same Algorithm, Verified to Fail
Run the identical GreedyCoinChange pseudocode — nothing about the algorithm itself changes — on a different denomination set: {1, 3, 4}, making change for 6.
4 (remaining 2), then 1 (remaining 1), then 1 (remaining 0) — [4, 1, 1], 3 coins. Independently computing the true optimum (again via dynamic programming, checking every combination systematically): [3, 3], 2 coins. Greedy's locally-best first choice — take the 4 — actively prevented it from reaching the genuinely better 2-coin answer.
4 first leaves a remainder of 2 — and with denominations {1,3,4}, 2 can only be made from two 1-coins, since there's no 2-coin and no way to use a 3 or a 4 without overshooting. The greedy choice wasn't wrong about being locally best — 4 genuinely is the single biggest step toward 6 — but it committed to a remainder that happens to be expensive to finish, and greedy never looks back to reconsider that commitment once made.
The Honest Rule for Trusting Greedy
Greedy works exactly when a locally optimal choice is guaranteed to never rule out a globally optimal solution — a property specific problems genuinely have (US coin denominations happen to; activity/interval scheduling and Huffman coding are two other classic examples) and other problems genuinely don't (the {1,3,4} denomination set above; the general knapsack problem is another well-known example). There's no way to tell just by looking at a problem casually — it has to be checked, either by testing against an independently-computed optimum (as this chapter just did) or by a formal proof (a topic for a more advanced algorithms course).
{1,3,4} case, proves greedy is not safe for that problem.
Where This Connects
| This chapter's finding | What it sets up |
|---|---|
| The exact same algorithm, verified optimal and verified suboptimal | Chapter 8's divide and conquer strategy is introduced specifically as an approach that doesn't rely on greedy's own risky "never look back" assumption |
| Cross-checking against an independently-computed reference optimum | The same verification discipline Chapter 10's capstone applies to whichever design strategy it ultimately chooses |
| Testing against brute force to catch a greedy failure | A direct, practical callback to Chapter 6's own brute-force baseline — small enough to serve as a trustworthy reference answer |
Hands-On Exercises
Using this chapter's own GreedyCoinChange pseudocode, hand-trace it on denominations {1, 3, 4} for amount=8. List each coin chosen and the remaining amount after each step, and state the final coin count.
Using this chapter's own explanation of why greedy fails on {1,3,4} for amount=6, explain in your own words why the failure specifically happens at the FIRST choice (picking the 4) rather than at a later step, and what would need to be true about the denomination set for this same kind of failure to never happen.
A developer says "greedy algorithms are unreliable and should be avoided in favor of always checking every possibility (Chapter 6's brute force)." Using this chapter's own verified US-coin results and Chapter 6's own explosive subset-count findings, explain what's wrong with treating this as a universal rule.
📄 View solutionChapter 7 Quick Reference
- Greedy: make the locally best choice at each step, never reconsider it
- Verified directly: greedy matches an independently-computed true optimum exactly on US coin denominations for three tested amounts (4, 6, and 9 coins)
- Verified directly: the identical algorithm, on denominations
{1,3,4}foramount=6, gives3coins where the true optimum (independently verified) is2— a real, measured greedy failure - Whether greedy is safe depends entirely on the problem's own structure, not on the algorithm itself — it has to be checked, not assumed
- Practical test: cross-check a candidate greedy algorithm against brute force or a reference optimum on small cases before trusting it on larger ones
- Next chapter: Divide and conquer — a design strategy that avoids greedy's own "never look back" risk by a different route