You have coins of denominations [1, 6, 10] and want to make change for 12. The greedy algorithm (always pick the largest coin that fits) returns [10, 1, 1] = 3 coins. What is the actual minimum?
A3 coins: [10, 1, 1]
B2 coins: [6, 6]
C2 coins: [10, 2] — but 2 doesn't exist
D4 coins: [1, 1, 1, 1, ...]
The greedy solution picks 10 first, then must use two 1s — total 3 coins. But [6, 6] achieves the same 12 using only 2 coins. This is the classic failure case showing that greedy does NOT always produce the optimal solution for coin change with arbitrary denominations. Standard denominations like US coins work greedily, but this example breaks that assumption.
Question 2 True / False
If a problem has both the greedy-choice property and optimal substructure, then a greedy algorithm is guaranteed to find the global optimum.
TTrue
FFalse
Answer: True
These two properties are exactly what makes greedy algorithms provably correct. The greedy-choice property ensures that a locally optimal choice is always part of some globally optimal solution. Optimal substructure ensures that after making a greedy choice, the remaining subproblem also has an optimal solution that can be built greedily. Together, they allow induction over the solution construction.
Question 3 Short Answer
What is an exchange argument, and why is it used to prove greedy algorithms correct?
Think about your answer, then reveal below.
Model answer: An exchange argument shows that any optimal solution can be transformed into the greedy solution without degrading its quality. You take a hypothetical optimal solution that differs from the greedy one, swap one non-greedy choice for the corresponding greedy choice, and show the result is no worse. Repeating this exchange converts the optimal solution into the greedy solution, proving the greedy solution is also optimal.
Intuition that a greedy choice 'seems best' is not a proof. The exchange argument is a formal proof technique: it shows that deviating from the greedy choice cannot help, by demonstrating a swap that is value-neutral or value-improving. This is necessary because greedy algorithms lack the exhaustive search of dynamic programming, so correctness must be argued directly from the structure of the problem.