3.7.4
Intuition Sabhi greedy algorithms ke peeche ek hi ideaEk greedy algorithm solution ko ek piece ek time mein banata hai — hamesha woh choice leta hai jo abhi sabse achhi lagti hai, aur kabhi wapas nahi sochta . Yeh global optimum tabhi deta hai jab problem ki ek special structure hoti hai: greedy-choice property (locally optimal choice kisi na kisi global optimum ka hissa hoti hai) aur optimal substructure (optimum mein subproblems ke optima hote hain).
WHY yeh fail ho sakta hai: greedy kabhi backtrack nahi karta, toh agar aaj ki best move kal ke liye nuksan kare, toh tum haar jaate ho. Poori skill yeh prove karna hai ki obvious move safe hai — usually ek exchange argument se: "koi bhi optimal solution lo; main apni greedy choice ko swap karke use worse nahi bana sakta."
n s i f i maximum number of mutually non-overlapping activities chunne hain (ek resource, jaise ek lecture hall).
Activities (start, finish): A(1,4) B(3,5) C(0,6) D(5,7) E(3,9) F(5,9) G(6,10) H(8,11) I(8,12) J(2,14) K(12,16)
Finish ke hisaab se sort karo (pehle se sorted hai). Trace:
A pick karo (f=4). last=4.B start 3 < 4 ✗. C start 0 ✗. D start 5 ≥ 4 ✓ → pick, last=7. Kyun? A ke baad pehla compatible.
E,F start <7 ✗. G start 6 <7 ✗. H start 8 ≥7 ✓ → pick, last=11.
I start 8 <11 ✗. J start 2 ✗. K start 12 ≥11 ✓ → pick.
Answer: {A, D, H, K} , size 4. Kyun optimal? har accepted job maximum future window free karta hai.
Common mistake Steel-man: "Start time se sort karo, yeh natural order hai"Kyun sahi lagta hai: chronological order fair lagta hai, aur tum events ko jaise aate hain process karte ho. Kyun galat hai: sabse pehle start karne wali activity sabse lambi ho sakti hai (jaise C(0,6)) aur schedule kha jaati hai. Fix: finish se sort karo; sabse pehle finish karne wala provably safe hai. Complexity: sort ke liye O ( n log n ) O ( n )
Knapsack capacity W i v i w i fractions le sakte ho. Total value ∑ x i v i ∑ x i w i ≤ W 0 ≤ x i ≤ 1
Intuition WHY value-per-weight jeetta haiCapacity ka har kilogram ek "slot" hai jo tum ek baar bechte ho. Use us item se bharna chahiye jo sabse zyada per kilogram pay kare: density v i / w i
Common mistake Steel-man: "0/1 knapsack bhi greedily solve hota hai"Kyun sahi lagta hai: densest-first universally optimal lagta hai. Kyun galat hai: indivisible items ke saath tum gap chodne par majboor ho sakte ho. Jaise W = 10 W = 50 A ( 60 , 10 ) , B ( 100 , 20 ) , C ( 120 , 30 ) A , B C fractional ke liye theek (240). Lekin 0/1 greedy A + B = 160 B + C = 220 Fix: 0/1 ko greedy nahi, dynamic programming chahiye.
W = 50 A ( v = 60 , w = 10 ) B ( v = 100 , w = 20 ) C ( v = 120 , w = 30 ) A = 6 , B = 5 , C = 4 A , B , C
A 50 → 40 60 Kyun? sabse zyada density.B 40 → 20 160 C 20/30 = 2/3 3 2 ⋅ 120 = 80
Total value = 240 Complexity O ( n log n )
Frequencies f 1 , … , f n prefix-free binary code banao (koi codeword doosre ka prefix nahi) jo total encoded length ∑ f i ⋅ ℓ i ℓ i
Intuition WHY do sabse chhote ko merge karoRare symbols lambi codes afford kar sakte hain; frequent symbols choti honi chahiye. Optimal tree mein do sabse kam-frequency wale symbols maximum depth par siblings hote hain — toh hum unhe ek super-symbol mein frequency f a + f b + = f a + f b
Worked example Worked example — frequencies a:5, b:9, c:12, d:13, e:16, f:45Min-heap merges (do sabse chhole pop karo):
5+9 = 14 (a,b). Heap: 12,13,14,16,45
12+13 = 25 (c,d). Heap: 14,16,25,45
14+16 = 30 . Heap: 25,30,45
25+30 = 55 . Heap: 45,55
45+55 = 100 = root.
Total cost = 14 + 25 + 30 + 55 + 100 = 224 Kyun internals ka sum? upar wali cost identity se.
Resulting lengths: f=1, c=3,d=3,e=3, a=4,b=4. Check: 45 ( 1 ) + 12 ( 3 ) + 13 ( 3 ) + 16 ( 3 ) + 5 ( 4 ) + 9 ( 4 ) = 45 + 123 + 56 = 224
Common mistake Steel-man: "Alphabetical / fixed order se merge karna theek hai"Kyun sahi lagta hai: koi bhi prefix tree decodable hota hai, toh order irrelevant lagta hai. Kyun galat hai: decodability ≠ minimum cost; ek fixed-length code rare symbols par bits waste karta hai. Fix: hamesha priority queue se do minimum frequencies pull karo. Complexity O ( n log n )
Recall Feynman: ek 12-saal ke bacche ko samjhaoActivity selection: tum ek theater mein jitni ho sake utni movies dekhna chahte ho — hamesha woh movie pick karo jo sabse pehle khatam hoti hai, taaki tum sabse jaldi free ho jao.
Fractional knapsack: tum powders ek bag mein scoop kar sakte ho; sabse pehle sabse mehenga-per-gram powder daalo jab tak bag bhar na jaye.
Huffman: jo words tum zyada bolte ho unhe chote secret-codes dete ho aur rare words ko lambe. Banane ke liye, do sabse rare words ko baar baar glue karte raho aur recombine karte raho, taaki rare wale sabse deep jayein (sabse lambe codes).
Mnemonic Greedy keys yaad karo"Finish Fast, Pour Pricey, Merge Mini."
Activity → sabse pehle F inish · Knapsack → sabse zyada P rice/weight · Huffman → do M inimum frequencies.
Recall Active recall — page band karo aur jawab do
Greedy ke optimal hone ke liye kaunsi property honi chahiye?
Earliest-finish shortest-duration se kyun better hai?
0/1 knapsack greedy kyun nahi karta lekin fractional karta hai?
Internal nodes ke terms mein Huffman tree ki cost kya hai?
Greedy algorithm definition Solution ko incrementally banata hai, locally best choice leta hai aur kabhi reconsider nahi karta.
Two properties needed for greedy optimality Greedy-choice property + optimal substructure.
Activity selection greedy rule Finish time se sort karo; baar baar sabse pehle finish hone wali compatible activity pick karo.
Why earliest-finish (not shortest/earliest-start) Pehle finish karna baaki activities ke liye maximum remaining time window chodta hai.
Activity selection complexity O ( n log n ) O ( n )
Fractional knapsack greedy rule Value/weight density descending se sort karo; items fully lo, aakhiri ka fraction lo.
Why fractional knapsack is greedy-solvable Fractions se tum capacity ko densest item se exactly fill kar sakte ho — exchange argument se koi waste nahi.
Why 0/1 knapsack is NOT greedy Indivisible items gaps force kar sakte hain; dynamic programming chahiye. Counterexample W=50, A(60,10),B(100,20),C(120,30).
Huffman core step Min-heap se do sabse kam-frequency nodes pop karo, summed frequency wale node mein merge karo, wapas push karo; n−1 baar repeat karo.
Huffman total cost formula Sabhi internal (merged) nodes ki frequencies ka sum.
Why merge the two smallest in Huffman Woh optimal tree mein sabse deep siblings hote hain; unhe merge karna har step par minimum cost add karta hai (exchange argument).
Huffman complexity O ( n log n )
Prefix-free code meaning Koi codeword doosre ka prefix nahi hota, isliye decoding unambiguous hoti hai.
General proof technique for greedy correctness Exchange argument — kisi bhi optimal solution ko ek aisa solution mein transform karo jo greedy choice contain kare bina cost badhaye.
Dynamic Programming — jab greedy fail ho tab zaruri (0/1 knapsack, edit distance).Priority Queue / Binary Heap — Huffman ki min-extraction ka engine.Exchange Argument — greedy correctness ke liye universal proof tool.Sorting Algorithms — activity selection aur knapsack mein O ( n log n ) Prefix Codes & Information Theory — Huffman Shannon entropy bound ke paas aata hai.Minimum Spanning Tree (Kruskal/Prim) — doosre classic greedy + exchange proofs.
no backtrack, risks failure
