Greedy problems — activity selection, fractional knapsack, Huffman coding (full algorithm): Exercises

Everything below reuses only the parent's vocabulary. A quick refresher of the three keys:

Level 1 — Recognition

Recall Solution L1-Q1

(a) earliest finish time. (b) ==highest density $v_{i} / w_{i}$ . (c) repeatedly merge the two minimum frequencies==. Mnemonic from parent: "Finish Fast, Pour Pricey, Merge Mini."

Recall Solution L1-Q2

No. Indivisible items → this is 0/1 knapsack, which greedy can get wrong; the correct tool is Dynamic Programming. The word "fractions" is the switch: allowed ⇒ greedy optimal; forbidden ⇒ DP.

Level 2 — Application

Recall Solution L2-Q1

Sort by finish: P(1,3), Q(2,5), R(4,7), S(1,8), T(5,9), U(8,10), V(9,11). Already sorted.

Pick P (f=3), last=3.
Q start 2 < 3 ✗. R start 4 ≥ 3 ✓ → last=7.
S start 1 ✗. T start 5 < 7 ✗. U start 8 ≥ 7 ✓ → last=10.
V start 9 < 10 ✗. Answer: {P, R, U}, size 3.

Recall Solution L2-Q1b

It does not affect correctness. Both candidates free the resource at the identical moment $f$ , so whichever you keep leaves the same future window $[f, \infty)$ for the remaining scan. The exchange argument still holds symmetrically. Consistent tie-breaker: when finish times tie, keep the one with the larger start (equivalently, the shorter activity). Rationale: it occupies less past time, never fewer future options, and gives a deterministic, reproducible ordering. Any fixed rule (e.g. by original index) is equally valid — just pick one and apply it everywhere.

Recall Solution L2-Q2

Densities: $X = 100/10 = 10$ , $Z = 120/20 = 6$ , $Y = 60/10 = 6$ . Tie between $Y$ and $Z$ at density 6 — either order is fine for the total (both are equally paying per kg).

Take X whole: room $20 \to 10$ , value $100$ .
Now $6$ per kg fills the last $10$ kg. Take Y whole (w=10): value $+ 60 = 160$ , room $\to 0$ . Bag full. (If we'd sliced Z instead: $10/20$ of Z $= \frac{1}{2} \cdot 120 = 60$ — same $160$ .) Total value $= 160$ .

Recall Solution L2-Q3

Min-heap: 2,3,7,8.

Pop 2,3 → merge 5 (g,h). Heap: 5,7,8. This merge deepens g and h by one bit each — it adds exactly the 5 occurrences beneath it, i.e. $+ 5$ bits.
Pop 5,7 → merge 12. Heap: 8,12. Adds $+ 12$ bits (everything under this new node gets one deeper).
Pop 8,12 → merge 20 = root. Adds $+ 20$ . Total bits $= \sum$ internals $= 5 + 12 + 20 = 37$ — exactly the WHY-callout identity. Lengths: j=1, i=2, g=3, h=3. Check: $8 (1) + 7 (2) + 2 (3) + 3 (3) = 8 + 14 + 6 + 9 = 37$ ✓. Total $= 37$ bits.

Level 3 — Analysis

Recall Solution L3-Q1

Activities: A(1,5), B(4,6), C(5,9).

Shortest-duration picks B (length 2) first. Then A(1,5) overlaps B, C(5,9) overlaps B → only {B}, size 1.
Finish-time greedy: sort A(f=5), B(f=6), C(f=9). Pick A (last=5); B start 4<5 ✗; C start 5≥5 ✓. → {A, C}, size 2. The short middle job straddles the two long-feasible jobs and blocks both — exactly the failure the parent warned about.

Recall Solution L3-Q2

Densities: A=6, B=5, C=4.

Density-greedy (0/1): take A (w10, room 40), take B (w20, room 20). C needs 30 > 20 → can't take (no fractions). Total $= 60 + 100 = 160$ .
True optimum: B + C $= 100 + 120 = 220$ , weight $20 + 30 = 50 \leq 50$ ✓. Greedy leaves 20 kg of room wasted because it can't slice C. $160 < 220$ — greedy loses. This is why 0/1 needs Dynamic Programming.

Recall Solution L3-Q3

Heap: 1,1,2,3,5.

1+1 = 2. Heap: 2,2,3,5.
2+2 = 4. Heap: 3,4,5.
3+4 = 7. Heap: 5,7.
5+7 = 12 = root. Total $= 2 + 4 + 7 + 12 = 25$ bits — each merge sum is the extra bits it contributes (WHY-callout), so summing them is the whole cost, no tree needed.

Level 4 — Synthesis

Recall Solution L4-Q1

No, greedy breaks. Counterexample: A(1,10, profit 100), B(1,3, profit 1), C(4,10, profit 1). Finish-time greedy first picks B (earliest finish), then C — total profit 2. But taking A alone gives 100. Earliest finish ignores value. Switch to Dynamic Programming: sort by finish, and for each activity choose $max (skip it, profit_{i} + best over activities finishing before its start)$ . The greedy-choice property fails because a low-count choice can carry huge profit — the exchange argument no longer holds.

Recall Solution L4-Q2

The rule "pop the two smallest" is never in doubt here: every node is 5, so any two smallest are two 5's. The only freedom is which two 5's you grab — a labelling choice, not an ordering choice.

Grab 5's #1,#2 → merge 10. Heap: {5,5,10}. Two smallest are the remaining 5,5 → merge 10. Heap: {10,10} → merge 20. Total $= 10 + 10 + 20 = 40$ .
Grab 5's #3,#4 first → merge 10. Heap: {5,5,10}. Again the two smallest are 5,5 → merge 10 → then 20. Total $= 10 + 10 + 20 = 40$ . Every valid run merges the two 5's first (the heap forces it — after the first merge the smallest two are still the leftover 5's, never the fresh 10). So the merge sums are always $10, 10, 20$ regardless of labels, giving the identical balanced tree: every symbol at depth 2, cost $4 \times 5 \times 2 = 40$ ✓. Lesson: ties give you freedom over labels, never over which frequencies to merge — and the cost identity depends only on the frequencies, so the total is pinned to 40 bits.

Recall Solution L4-Q3

Densities: M=3, N=3, O=1.6. Both M and N pay 3 per kg. Total capacity 15 lets us take both M (10kg) and N (5kg) whole: value $30 + 15 = 45$ , bag full, O never reached. Order among the tie is irrelevant because we fit both. Total $= 45$ . (If capacity were 12, we'd take one whole and slice the other — but since both are density 3, either choice yields the same value per kg for the sliced part, so the total is still order-independent.)

Level 5 — Mastery

Recall Solution L5-Q1

Proposal: $\frac{1}{2}$ of Q uses 10 kg, value $\frac{1}{2} \cdot 50 = 25$ . Bag full. Exchange: remove all 10 kg of Q (value drops by 25) and add 10 kg of P (value up by $10 \cdot d_{P} = 10 \cdot 4 = 40$ ). Net change $= + 40 - 25 = + 15 > 0$ . New solution: P whole, value $40$ . Since $40 > 25$ , the denser-first solution strictly wins — exactly the parent's exchange argument $ε (d_{i} - d_{j}) > 0$ with $ε = 10$ , $d_{i} - d_{j} = 4 - 2.5 = 1.5$ , giving $10 \cdot 1.5 = 15$ . Totals: proposal 25, greedy 40.

Recall Solution L5-Q2

Fixed-length: 3 bits each $\times$ total frequency 100 $= 300$ bits. Huffman $= 224$ bits (parent). $224 \leq 300$ ✓ — Huffman saves $300 - 224 = 76$ bits, a $76/300 = 25.33%$ reduction. The savings come from giving the frequent f (freq 45) a 1-bit code instead of 3 bits.

Recall Solution L5-Q3

Huffman (two minimum first): the two smallest are a(1), b(1) → merge 2. Heap: {2, 100}. Merge $2 + 100 =$ 102 = root. Total $= 2 + 102 = 104$ bits. Lengths: c=1, a=2, b=2 → $100 (1) + 1 (2) + 1 (2) = 104$ ✓. The frequent c sits at depth 1 (a 1-bit code) — exactly where a hot symbol belongs. Bad "merge-the-frequent-one-early" heuristic: it grabs c(100) and pairs it with a(1) → merge 101. Heap: {1, 101}. Merge $1 + 101 =$ 102 = root. Total $= 101 + 102 = 203$ bits. Lengths: a=2, c=2, b=1 → $1 (2) + 100 (2) + 1 (1) = 203$ ✓. Here c was buried at depth 2, so its 100 occurrences each cost an extra bit. Huffman 104 vs bad heuristic 203 — difference $= 99$ bits. The rule two minimum first is precisely what keeps the frequent symbol shallow; any heuristic that pairs the frequent symbol early pushes it deep and nearly doubles the cost.

Recall Full active-recall checklist

Sort key for activities ::: earliest finish time Sort key for fractional knapsack ::: density $v_{i} / w_{i}$ descending Huffman merge rule ::: pop and merge the two minimum frequencies Total Huffman bits formula ::: sum of all internal-node frequencies Why that formula holds ::: each merge deepens its subtree by one bit, adding exactly its frequency-many bits When does knapsack switch to DP ::: when items are indivisible (0/1) When does activity selection switch to DP ::: when activities carry weights/profits Tie-break for equal finish times ::: any fixed rule works; e.g. keep the larger start / shorter activity Proof technique linking all three ::: Exchange Argument

Related: Sorting Algorithms (every greedy here starts with an $O (n lo g n)$ sort), Priority Queue / Binary Heap (Huffman's engine), Prefix Codes & Information Theory, Minimum Spanning Tree (Kruskal/Prim) (another exchange-argument greedy).