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

3.7.4 · D4 · Coding › Algorithm Paradigms › Greedy problems — activity selection, fractional knapsack, H

Neeche sab kuch sirf parent ki vocabulary use karta hai. Teeno keys ka ek quick refresher:

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==. Parent se mnemonic: "Finish Fast, Pour Pricey, Merge Mini."

Recall Solution L1-Q2

Nahin. Indivisible items → yeh 0/1 knapsack hai, jise greedy galat kar sakta hai; sahi tool Dynamic Programming hai. Word "fractions" switch hai: allowed ⇒ greedy optimal; forbidden ⇒ DP.

Level 2 — Application

Recall Solution L2-Q1

Finish ke hisaab se sort karo: P(1,3), Q(2,5), R(4,7), S(1,8), T(5,9), U(8,10), V(9,11). Pehle se sorted hai.

P lo (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

Correctness par koi fark nahin padta. Dono candidates resource ko identical moment $f$ par free karte hain, isliye jo bhi tum rakho woh remaining scan ke liye same future window $[f, \infty)$ chhod deta hai. Exchange argument symmetrically hold karta hai. Consistent tie-breaker: jab finish times tie karein, wo activity rakho jiska start bada ho (equivalent mein, shorter activity). Rationale: yeh kam past time occupy karta hai, future options kabhi kam nahin hote, aur ek deterministic, reproducible ordering deta hai. Koi bhi fixed rule (jaise original index se) equally valid hai — bas ek choose karo aur har jagah apply karo.

Recall Solution L2-Q2

Densities: $X = 100/10 = 10$ , $Z = 120/20 = 6$ , $Y = 60/10 = 6$ . $Y$ aur $Z$ ke beech density 6 par tie hai — total ke liye koi bhi order theek hai (dono per kg equally pay kar rahe hain).

X whole lo: room $20 \to 10$ , value $100$ .
Ab $6$ per kg last $10$ kg fill karta hai. Y whole lo (w=10): value $+ 60 = 160$ , room $\to 0$ . Bag full. (Agar hum Z slice karte: $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. Yeh merge g aur h ko ek bit aur gehra karta hai — yeh exactly unke neeche 5 occurrences add karta hai, matlab $+ 5$ bits.
Pop 5,7 → merge 12. Heap: 8,12. $+ 12$ bits add karta hai (is naye node ke neeche sab kuch ek aur gehra ho jaata hai).
Pop 8,12 → merge 20 = root. $+ 20$ add karta hai. Total bits $= \sum$ internals $= 5 + 12 + 20 = 37$ — exactly 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 pehle B (length 2) pick karta hai. Phir A(1,5) B se overlap karta hai, C(5,9) B se overlap karta hai → sirf {B}, size 1.
Finish-time greedy: sort A(f=5), B(f=6), C(f=9). A lo (last=5); B start 4<5 ✗; C start 5≥5 ✓. → {A, C}, size 2. Chhota middle job do long-feasible jobs ke beech mein aata hai aur dono ko block karta hai — exactly woh failure jiske baare mein parent ne warn kiya tha.

Recall Solution L3-Q2

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

Density-greedy (0/1): A lo (w10, room 40), B lo (w20, room 20). C ko 30 chahiye > 20 → nahin le sakte (fractions nahin). Total $= 60 + 100 = 160$ .
True optimum: B + C $= 100 + 120 = 220$ , weight $20 + 30 = 50 \leq 50$ ✓. Greedy 20 kg room waste karta hai kyunki woh C slice nahin kar sakta. $160 < 220$ — greedy haara. Isliye 0/1 ko Dynamic Programming chahiye.

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 — har merge sum wahi extra bits hai jo woh contribute karta hai (WHY-callout), isliye unhe sum karna poori cost hai, koi tree zaroorat nahin.

Level 4 — Synthesis

Recall Solution L4-Q1

Nahin, greedy toot jaati hai. Counterexample: A(1,10, profit 100), B(1,3, profit 1), C(4,10, profit 1). Finish-time greedy pehle B pick karta hai (earliest finish), phir C — total profit 2. Lekin sirf A lene se 100 milta hai. Earliest finish value ignore karta hai. Dynamic Programming par switch karo: finish se sort karo, aur har activity ke liye $max (skip it, profit_{i} + best over activities finishing before its start)$ choose karo. Greedy-choice property fail ho jaati hai kyunki ek low-count choice huge profit carry kar sakti hai — exchange argument ab hold nahin karta.

Recall Solution L4-Q2

Rule "do sabse chhote pop karo" yahan kabhi doubt mein nahin hai: har node 5 hai, isliye koi bhi do smallest do 5's hain. Sirf yahi freedom hai ki tum kaun se do 5's grab karo — yeh ek labelling choice hai, ordering choice nahin.

5's #1,#2 grab karo → merge 10. Heap: {5,5,10}. Do sabse chhote baaki 5,5 hain → merge 10. Heap: {10,10} → merge 20. Total $= 10 + 10 + 20 = 40$ .
Pehle 5's #3,#4 grab karo → merge 10. Heap: {5,5,10}. Phir bhi do sabse chhote 5,5 hain → merge 10 → phir 20. Total $= 10 + 10 + 20 = 40$ . Har valid run pehle do 5's merge karta hai (heap force karta hai — pehle merge ke baad sabse chhote do abhi bhi baaki 5's hain, fresh 10 nahin). Isliye merge sums hamesha $10, 10, 20$ hote hain chahe labels kuch bhi hon, same balanced tree dete hain: har symbol depth 2 par, cost $4 \times 5 \times 2 = 40$ ✓. Lesson: ties tumhe labels par freedom deti hain, kabhi is par nahin ki kaun si frequencies merge karni hain — aur cost identity sirf frequencies par depend karti hai, isliye total 40 bits par pinned hai.

Recall Solution L4-Q3

Densities: M=3, N=3, O=1.6. M aur N dono 3 per kg pay karte hain. Total capacity 15 hum dono M (10kg) aur N (5kg) whole le sakte hain: value $30 + 15 = 45$ , bag full, O kabhi reach nahin hua. Tie mein order irrelevant hai kyunki hum dono fit kar lete hain. Total $= 45$ . (Agar capacity 12 hoti, hum ek whole leke doosre ko slice karte — lekin dono density 3 hain, isliye sliced part ke liye either choice same value per kg deti hai, isliye total abhi bhi order-independent hai.)

Level 5 — Mastery

Recall Solution L5-Q1

Proposal: $\frac{1}{2}$ of Q 10 kg use karta hai, value $\frac{1}{2} \cdot 50 = 25$ . Bag full. Exchange: Q ke saare 10 kg hatao (value 25 girti hai) aur P ke 10 kg add karo (value $10 \cdot d_{P} = 10 \cdot 4 = 40$ badhti hai). Net change $= + 40 - 25 = + 15 > 0$ . Nayi solution: P whole, value $40$ . Kyunki $40 > 25$ , denser-first solution strictly jeetata hai — exactly parent ka 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 $300 - 224 = 76$ bits bachata hai, $76/300 = 25.33%$ reduction. Savings frequent f (freq 45) ko 3 bits ki jagah 1-bit code dene se aati hain.

Recall Solution L5-Q3

Huffman (do minimum pehle): do sabse chhote a(1), b(1) hain → 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$ ✓. Frequent c depth 1 par baitha hai (1-bit code) — exactly wahan jahan ek hot symbol belong karta hai. Bad "merge-the-frequent-one-early" heuristic: yeh c(100) grab karta hai aur a(1) ke saath pair karta hai → 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$ ✓. Yahan c depth 2 par dab gaya, isliye uske 100 occurrences har ek ko ek extra bit pay karna pada. Huffman 104 vs bad heuristic 203 — difference $= 99$ bits. Rule two minimum first exactly wahi hai jo frequent symbol ko shallow rakhta hai; koi bhi heuristic jo frequent symbol ko early pair karta hai use deep dhakel deta hai aur cost almost double kar deta hai.

Recall Full active-recall checklist

Activities ke liye sort key ::: earliest finish time Fractional knapsack ke liye sort key ::: density $v_{i} / w_{i}$ descending Huffman merge rule ::: do minimum frequencies pop aur merge karo Total Huffman bits formula ::: saare internal-node frequencies ka sum Woh formula kyun hold karta hai ::: har merge apne subtree ko ek bit aur gehra karta hai, exactly apni frequency-many bits add karta hai Knapsack DP par kab switch hota hai ::: jab items indivisible hoin (0/1) Activity selection DP par kab switch hoti hai ::: jab activities weights/profits carry karein Equal finish times ke liye tie-break ::: koi bhi fixed rule kaam karta hai; jaise bada start / shorter activity rakho Teeno ko link karne wali proof technique ::: Exchange Argument

Related: Sorting Algorithms (yahan har greedy ek $O (n lo g n)$ sort se shuru hoti hai), Priority Queue / Binary Heap (Huffman ka engine), Prefix Codes & Information Theory, Minimum Spanning Tree (Kruskal/Prim) (ek aur exchange-argument greedy).