Micro-questions over the greedy module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The failure mode

1. Give the mountain trail illustration.

Answer

Two branches: +150m, or +200m leading to −300m. Greedy takes +200 and ends at −100m; the optimal choice takes +150. A locally attractive choice locks out a better long-term outcome.

2. Name two problems where greedy works and two where it fails.

Answer

✅ Activity selection (take the job that finishes earliest) and Huffman coding (merge the two lowest-frequency nodes).
❌ Coin change with arbitrary denominations and 0/1 knapsack (value-per-weight ignores capacity interactions).


B. The vocabulary

3. What is a greedy choice?

Answer

The locally optimal decision made at each step without reconsidering past choices.

4. What is an exchange argument?

Answer

A proof showing that swapping any greedy choice for any alternative can never improve the outcome.

5. Is a greedy algorithm a heuristic?

Answer

No. A greedy algorithm is an exact algorithm producing the globally optimal answer when applicable — not an approximation.

6. What property do both greedy and DP require?

Answer

Optimal substructure — an optimal solution composed of optimal solutions to subproblems.


C. The coin change trap

7. Coins , amount 11 — does greedy work?

Answer

Yes: = 3 coins, which is optimal.

8. Coins , amount 6 — what happens?

Answer

Greedy takes 4 first, leaving 2, needing two 1s — 3 coins. Optimal is = 2.

9. State the failure precisely.

Answer

Taking 4 greedily closes off the path. The locally largest coin blocks the globally best combination.

10. What does that tell you about the problem statement?

Answer

Nothing in it distinguishes the two coin sets — which is why greedy must be proved, not felt.


D. A provably correct greedy

11. State the canoe pairing problem.

Answer

Pair people of known weights into canoes of maximum capacity . Minimise the number of canoes.

12. State the greedy strategy.

Answer

Always try to pair the heaviest remaining person with the lightest remaining person. If they exceed capacity, the heaviest goes alone.

13. Give the exchange argument.

Answer

Consider the heaviest person . If can share with anyone, they can share with the lightest person — because if an optimal solution pairs with a heavier , swapping and can only maintain or improve the result, since fits anywhere did.

14. What does that licence you to do?

Answer

Commit to the greedy choice and reduce the problem to the remaining people — which is exactly the inductive proof structure for correctness.

15. What familiar pattern does the implementation use?

Answer

Two pointers — left at the lightest, right at the heaviest, converging from both ends of the sorted array.

16. Why does right -= 1 happen unconditionally?

Answer

The heaviest person is always seated — either paired with the lightest, or alone. Only the left pointer is conditional.


E. Choosing

17. Give the three-row decision guide.

Answer
SignalUse
Locally best provably never worse (exchange argument holds)Greedy — fastest when it applies
Choices interact — “best now” can block a better futureDynamic programming
Small problem, need a correct baselineBrute force

18. State the key test.

Answer

“Can I prove the greedy choice is at least as good as any alternative using an exchange argument?” If yes, greedy is safe. If not, switch to DP.

19. What is the typical complexity of a greedy algorithm?

Answer

time — dominated by the sort that establishes the greedy criterion — and auxiliary space, since no memo table is needed.

20. What step do people most often miss?

Answer

The sort. Most greedy algorithms require first sorting by the greedy criterion — finishing time, weight, cost-per-unit.

21. Summarise the lesson in one sentence.

Answer

Greedy is exact when an exchange argument shows the local choice is never worse — and without that proof it is just a guess that happens to work on your examples.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Greedy Algorithms