Greedy Algorithms
Making the locally-best choice at each step and never revisiting it — correct only when the problem has the right structural guarantee.
Try answering in your head first, then click a question to check the model answer.
Q1.What does it mean for a problem to have the "greedy-choice property," and why does it matter?(show answer)
It means a globally optimal solution can always be reached by making the best-looking choice at the current step, without ever needing to reconsider that choice later — no backtracking required. This is what justifies using a greedy algorithm at all; without this property (as in general 0/1 knapsack), a locally optimal choice can lock you out of the actual best overall solution, and you need a different technique (like dynamic programming) instead.
Q2.Explain the greedy solution to the activity selection problem and why picking the earliest finish time works.(show answer)
Sort activities by finish time, then greedily pick each activity that starts after the previously selected one ends. Picking the earliest-finishing valid activity at each step leaves the maximum possible remaining time for future activities — any other valid choice at that step finishes no earlier, so it can never leave more room for subsequent picks. This greedy choice can be proven, via an exchange argument, to never be worse than any other valid first choice.
Q3.Why does the "always pick the largest coin" greedy strategy fail for coin denominations {1, 3, 4} with a target of 6?(show answer)
Greedy picks 4 first (largest ≤ 6), leaving 2, then two more 1-coins — 3 coins total (4+1+1). But the actual optimal is two 3-coins (3+3) — only 2 coins. Greedy's locally optimal choice (always take the biggest coin) doesn't account for how that choice constrains the remaining subproblem, so it isn't globally optimal for this particular denomination set — this is a classic counterexample showing greedy needs the greedy-choice property to hold, which it doesn't for arbitrary coin systems.
Q4.How do you generally prove a greedy algorithm is correct?(show answer)
Two common approaches: an exchange argument (show that any optimal solution can be transformed into the greedy solution, step by step, without making it worse — proving greedy is at least as good), or proving optimal substructure combined with the greedy-choice property (show the greedy choice, plus an optimal solution to the remaining subproblem, gives an optimal solution overall). Without such a proof, a greedy-looking approach might just be a plausible heuristic that fails on some inputs, as with the coin-change counterexample.