Unit 4.3 · about 4 h
115 / 324Greedy choice, optimal substructure and exchange arguments
Greedy is the shortest path from idea to code and the easiest place to be confidently wrong. The proof is the algorithm, so write it before the loop.
- derive
You can now
- State the greedy-choice property and optimal substructure of a new problem in one paragraph each, before writing any loop.
- Prove a greedy rule with an exchange argument that preserves feasibility and never worsens the objective.
- Prove a greedy rule with a staying-ahead invariant that compares the greedy prefix against every optimal prefix.
Covers
- Greedy-choice property and optimal substructure
- Exchange, staying-ahead and cut arguments
Study, in this order
3 steps
- Greedy thinking: when local choices win, and when they do notDSA Handbook - recursion, backtracking and greedy
When greedy is provably correct: The exchange argument; Greedy stays ahead; A working example: Partition Labels
Depth · Use the Where greedy fails section as a preview of the next unit. Counterexample drills live there.
- Huffman encodingDSA Handbook - recursion, backtracking and greedy
The algorithm; Watching it run; Why Huffman codes are optimal prefix codes: the sibling exchange and the optimal-substructure step
- Greedy Algorithms, Chapter 4Algorithms - recursion, backtracking and greedy
4.1 Storing Files on Tape for the first exchange argument, 4.3 General Pattern for the exchange template, and 4.4 Huffman Codes (printed pp. 159-170)
Depth · Erickson proves everything by exchange; take stays-ahead from the handbook. Skip 4.5 Stable Matching.
Focus on
- Exchange has a fixed shape: take an optimal solution, swap its first differing choice for the greedy one, show validity kept and the objective not worse, then induct on the rest.
- Staying-ahead has a different shape: the greedy frontier dominates every optimal prefix at each step, as with Jump Game max reach. Pick the template that matches the state you can compare.
- Optimal substructure must hold after the greedy choice. In Huffman coding, merging the two least frequent symbols leaves a smaller instance whose optimum sits inside the full optimum through the weight recurrence.
- Partition Labels is the stays-ahead drill: last occurrence table, extend the part end, cut at \(i = \text{end}\), in \(O(n)\) time and \(O(1)\) extra space.
Reproduce closed-book
ababcbacadefegdehijhklij to get [9, 7, 8]. Closed book, write the Huffman exchange step: swapping a least frequent symbol into a deepest sibling leaf changes total cost by at most zero.Traps
- Proving by example. Passing samples shows the code runs; only the exchange or staying-ahead step shows no optimal solution beats it.
- An exchange that breaks feasibility. Swapping must keep the prefix-free sibling structure in Huffman coding and disjointness in scheduling, or the transformed optimum is not a valid candidate.
- Staying ahead on a measure that does not imply the objective. Largest-coin-first on coins
[1, 3, 4]with target 6 leads on amount covered after one coin (4 against 3), yet needs 3 coins (\(4 + 1 + 1\)) against the optimal 2 (\(3 + 3\)).
Practice
Attempt cold. Example gas [1, 2, 3, 4, 5] with cost [3, 4, 5, 1, 2] returns 3; gas [2, 3, 4] with cost [3, 4, 3] returns minus 1.
After submitting, read the DSA Handbook Jump games and gas station chapter (Claims 1 and 2) and the AlgoMaster Gas Station lesson (https://algomaster.io/learn/dsa/gas-station), and restate your loop invariant in their terms.
Self-test
-
When do you reach for exchange, and when for staying-ahead?
Exchange fits when any optimum can be rewritten choice by choice into greedy form. Staying-ahead fits when greedy maintains a frontier, such as reach or coverage, that dominates every optimal prefix at each step. -
State the Huffman exchange computation.
Let \(x\) be a least frequent symbol and \(b\) a deepest leaf. Swapping their positions changes weighted path length by \((\text{freq}[b] - \text{freq}[x]) \times (\text{depth}[x] - \text{depth}[b])\), which is at most zero since \(\text{freq}[b]\) is at least \(\text{freq}[x]\) and \(\text{depth}[x]\) is at most \(\text{depth}[b]\). Repeat until the two least frequent symbols are deepest siblings. -
Why does \(\text{total gas} - \text{total cost}\) at least zero guarantee a valid start?
Start after the station where cumulative surplus hits its minimum. Every partial sum from there stays nonnegative, so the tank never empties over the full circuit. -
What optimal-substructure claim does Huffman coding need after the greedy merge?
Merging the two least frequent symbols into one parent leaves a smaller coding instance, and an optimal tree for the smaller instance extends to an optimal tree for the original through the weight recurrence.
Completion criterion
Stop when
Gas Station is accepted from a cold attempt, and you can write the Huffman exchange step and the total-surplus argument without notes.
Mark passed, then open 4.4 Only mark this when you can do it without notes.Leads to
- 4.4 Greedy counterexamples and interval scheduling Practice refuting plausible greedy rules, then prove earliest-finish scheduling.
- 5.1 Dynamic programming states, transitions and base cases Optimal substructure without a safe greedy choice forces dynamic programming.
Comes after
- 3.7 Minimum spanning trees with Kruskal and PrimThe cut property is the exchange argument in its cleanest form; carry it into greedy correctness proofs.
- 5.1 Dynamic programming states, transitions and base casesSeparate DP recurrences from greedy-choice arguments with proofs or counterexamples.
Resources for this unit
- DSA Handbook - recursion, backtracking and greedy Study Part 7, Part 10 and the relevant foundations on recursion and probability. Write the state definition or greedy claim before opening code.
- Algorithms - recursion, backtracking and greedy Use the recursion, backtracking, divide-and-conquer and greedy chapters for recurrence derivations, proof templates and counterexamples.
Also in this section
- AlgoMaster DSA - decomposition and greedy slice Attempt N-Queens and Gas Station cold, then implement reservoir sampling and test its output distribution over fixed-seed trials. Add another judged problem only for a diagnosed weakness.
- MIT 6.042J - probability and randomized algorithms Use the probability, expectation and concentration readings to derive sampling probabilities and distinguish expected from high-probability guarantees.
- Algorithms lecture notes - randomized algorithms Use note 1 Discrete Probability, note 2 Nuts and Bolts (randomized quicksort, with QuickSelect in its exercises), note 4 Tail Inequalities and note 5 Hashing to derive expected costs, separate expected from high-probability guarantees, and analyze hashing behavior.