Algorithms from zero
Greedy: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before opening the model answer. Reconstructing the exchange argument from scratch is what turns it from a thing you recognise into a thing you can wield.
Reconstruct the unit’s spine — the two conditions for greedy correctness, the three moves of the exchange argument, the interval sort keys, and the Gas Station invariant — without looking back at the lessons.
- 01What two properties must a problem have for a greedy algorithm to be optimal, and what does each mean?
- 02State the three moves of the exchange argument and the direction of reasoning that makes it work.
- 03Why does 'no worse' (rather than 'strictly better') suffice in the exchange step, and why is that the right strength?
- 04For interval problems, which sort key goes with which goal, and why is each correct?
- 05How does 'greedy stays ahead' differ from the exchange argument, and when would you use it?
- 06In Gas Station, what global condition decides feasibility, and why is resetting the candidate start to i+1 safe?
If you reconstructed each answer from memory you hold the unit’s spine: greedy is optimal only with the greedy-choice property plus optimal substructure; the exchange argument proves safety by reshaping an optimum toward greedy with no-worse swaps (and a missing swap is itself a proof of failure); interval problems live or die on the sort key — finish for maximization, start for merging, start-and-end sweep for rooms; and scan greedies like Gas Station decide feasibility from a global invariant while a self-correcting reset finds the start in one pass.