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

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

Do words jinhe hum poore waqt use karte hain:

greedy-choice property = woh choice jo abhi sabse achhi lagti hai woh kisi global optimum ka hissa hoti hai, isliye tumhe use kabhi undo nahi karna padta.
optimal substructure = woh choice karne ke baad, baaki ke best answer ka matlab sirf usi problem ke ek chhote version ka best answer hai.

True or false — justify karo

Activity selection ke liye sort by finish time hamesha sort by start time se behtar hota hai.

True — earliest-finish resource ko sabse jaldi free karta hai, jo provably safe hai; earliest-start ek lamba job pick kar sakta hai jo sab kuch block kar de (e.g. C(0,6) poore schedule ko hada deta hai).

Fractional knapsack aur 0/1 knapsack dono "densest item first" se optimally solve hote hain.

False — sirf fractional version mein. 0/1 mein tum last item ko slice nahi kar sakte, isliye ek high-density item ek aisa gap chhod sakta hai jo fill nahi hota; 0/1 ko Dynamic Programming chahiye.

Ek optimal Huffman tree mein do sabse rare symbols hamesha deepest level par siblings hote hain.

True — yahi toh exchange argument prove karta hai; sabse rare symbols ko sabse lambe codes dena hi total bits minimize karta hai.

Ek greedy algorithm kisi earlier choice ko revisit karke change kar sakta hai agar baad ke step mein koi better option dikhe.

False — definition ke hisaab se greedy kabhi reconsider nahi karta; woh non-backtracking hi reason hai ki hume har choice ko trust karne se pehle prove karna hota hai ki woh safe hai.

Har problem jisme optimal substructure ho use greedily solve kiya ja sakta hai.

False — optimal substructure 0/1 knapsack aur bahut saare DP problems mein bhi hoti hai. Tumhe saath mein greedy-choice property bhi chahiye; uske bina DP zaroori hai.

Huffman ka total cost saare internal nodes ki frequencies ke sum ke barabar hota hai.

True — frequency

g

ka har merge dono subtrees ko ek level aur gehra kar deta hai, theek

g

bits add karta hai; merges par sum karne se total milta hai, e.g.

14 + 25 + 30 + 55 + 100 = 224

Agar do activities ki finish time same ho, toh algorithm ka answer is baat par depend karta hai ki tum pehle kaunsa pick karte ho.

Count ke liye False — tie-breaking kaunsa set output hoga yeh badal sakta hai, lekin activities ki maximum sankhya par koi fark nahi padta, kyunki dono tied jobs resource ko usi instant par free karti hain.

Sorting hi teeno algorithms mein asli bottleneck hai.

True — har ek

O (n lo g n)

hai jo sorting se dominate hota hai (ya Huffman ke liye heap operations via Priority Queue / Binary Heap); actual greedy scan/merge linear hai.

Fixed-length code kabhi bhi total bits mein Huffman code se behtar nahi ho sakta.

True — Huffman prefix codes mein provably optimal hai, aur fixed-length bhi ek aisa hi prefix code hai, isliye Huffman kam se kam utna hi chhota hoga (equal sirf tab jab saari frequencies equal hon).

Error dhundho

"Greedy activity selection: sabse chhoti activity pehle pick karo kyunki woh sabse kam time use karti hai."

Galat metric. Ek chhoti job do aur otherwise-compatible lambi jobs ke beech boundary par aa sakti hai, dono ko block karke. Safe key hai earliest finish, na ki sabse chhoti duration.

"Fractional knapsack ke liye, value descending se sort karo aur sabse valuable items lo."

Galat key. Ek bahut high-value item ka weight bhi bahut zyada ho sakta hai aur woh capacity hog kar sakti hai. Sahi key hai density

v_{i} / w_{i}

— us resource ke per kilogram value jise tum ration kar rahe ho.

"Huffman: pehle do sabse zyada frequent symbols merge karo taaki common symbols ek subtree share karein."

Ulta hai. Tum do minimum frequencies merge karte ho; chhote wale merge karne se sabse rare symbols gehre ho jaate hain, unhe lambe codes milte hain aur frequent symbols shallow rehte hain.

"Exchange argument greedy ko optimal prove karta hai har possible solution ko try karke aur compare karke."

Koi brute force nahi hota. Ek Exchange Argument ek arbitrary optimal solution leta hai aur dikhata hai ki tum greedy choice swap in kar sakte ho bina use kharab kiye — ek single structural swap, enumeration nahi.

"Fractional knapsack mein tumhe bag aadha khaali chhodni pad sakti hai agar items exactly fit nahi karte."

Kabhi nahi — kyunki fractions allowed hain, tum hamesha last space ko next-densest item ke ek tukde se bharte ho, isliye bag exactly full ho jaata hai (jab tak total weight < W na ho).

"Koi bhi prefix-free code optimal hota hai kyunki har prefix code uniquely decodable hota hai."

Do properties ko confuse kar raha hai. Decodability guarantee karta hai ki tum code padh sako, na ki woh chhota hai. Optimality ka matlab

\sum f_{i} ℓ_{i}

minimize karna hai, jo sirf Huffman ka merge order achieve karta hai.

"Greedy 0/1 knapsack par fail karta hai, toh fractional knapsack par bhi fail karna chahiye."

Galat generalization. Fraction hi greedy ko bachata hai: yeh woh indivisibility hata deta hai jo 0/1 case mein unfillable gaps create karta hai.

Why questions

Ek lower-density item se weight uthake higher-density item mein dalna fractional greedy ko optimal kyun prove karta hai?

Kyunki value change

ε (d_{i} - d_{j}) > 0

hota hai jab bhi

d_{i} > d_{j}

— jo bhi solution sabse dense pehle max nahi karta use strictly improve kiya ja sakta hai, isliye woh optimal nahi tha.

Huffman ke do least-frequent symbols shallowest ki jagah deepest kyun hone chahiye?

Depth = codeword length, aur lambe codes rare symbols ko jaane chahiye taaki unki length ek chhoti frequency se multiply ho — total

\sum f_{i} ℓ_{i}

minimize karte hue.

Ek optimal solution ke earliest-finisher

a_{k}

ko global earliest-finisher

a_{1}

se replace karna feasible kyun rehta hai?

Kyunki

f_{a_{1}} \leq f_{a_{k}}

, isliye

a_{1}

kisi aisi cheez se conflict nahi karta jo

a_{k}

already nahi karti thi — woh resource utni jaldi ya usse bhi jaldi free karti hai, isliye baaki ka schedule fit rehta hai.

Huffman ke liye sorted list ki jagah min-heap natural data structure kyun hai?

Har step ko do current minimums aur ek naye merged node ka insertion chahiye; ek Priority Queue / Binary Heap dono kaam

O (lo g n)

mein karta hai, jabki har baar list ko re-sort karna

O (n)

lagta hai.

Greedy apni 0/1 knapsack mistakes theek karne ke liye simply "ek step aage dekh" kyun nahi sakta?

Khatarnak combination kaafi steps baad aa sakta hai — ek locally best pick ek aisi combination ko exclude kar sakta hai jo sirf kaafi choices ke baad visible hoti hai, aur yahi wajah hai ki subproblems par exhaustive (Dynamic Programming) zaroori hota hai.

Do sabse chhoti frequencies merge karna har step par sabse kam possible cost kyun add karta hai?

Har merge

f_{a} + f_{b}

total ko charge karta hai; do sabse chhoti available frequencies choose karna us step par woh charge minimize karta hai, aur greedy-choice proof dikhata hai ki yeh local minima milke global minimum banate hain.

Edge cases

Activity selection mein agar saari activities mutually non-overlapping hoon toh kya hoga?

Tum sabko pick karte ho — greedy scan kabhi kisi ko reject nahi karta, aur count

n

ke barabar hota hai.

Agar saari

n

activities ek common instant par overlap karti hon toh?

Tum exactly ek pick kar sakte ho — earliest finisher choose karne ke baad, koi aur start uski finish se

\geq

nahi hoti, isliye answer size 1 hai.

Fractional knapsack jab total item weight

\leq W

ho: answer kya hai?

Har item poori lo; bag mein room bachega aur total value simply

\sum v_{i}

hogi — koi fraction kabhi zaroori nahi.

Fractional knapsack jab

W = 0

ho: greedy kya return karta hai?

Kuch fit nahi hota, isliye sab

i

ke liye

x_{i} = 0

aur total value

0

hai; "pehla overflowing item" bilkul pehla item hai, fraction

0/ w_{i}

liya gaya.

Huffman jab single symbol ho (

n = 1

): use kitni code length milti hai?

Koi merge nahi hota, isliye koi bit kabhi assign nahi hota; ek akela symbol technically cost formula ke hisaab se

0

bits leta hai (practically ek degenerate 1-bit code use kiya jaata hai taaki transmittable ho sake).

Huffman jab saari

n

frequencies equal hon: kaisa tree banta hai?

Ek balanced tree jisme codes ki length

⌈ lo g_{2} n ⌉

hoti hai (ya kuch leaves ke liye ek bit kam agar

n

power of two nahi hai) — fixed-length code ke identical, jo yahan already optimal hai.

Agar do Huffman merges frequency par tie karein — kya total cost change hota hai?

Nahi — alag tie-breaks alag shapes (aur alag individual code lengths) produce kar sakte hain, lekin minimum total bit-count

\sum f_{i} ℓ_{i}

invariant hota hai.

Activity selection jab single activity ho (

n = 1

): kya return hota hai?

Woh ek activity — greedy hamesha pehle (earliest finisher) ko pick karta hai, aur scan karne ke liye kuch bacha nahi.

Recall Band karne se pehle ek-line self-check

Mnemonic aur woh key bolo jis par har algorithm sort/heap karta hai. Answer ::: "Finish Fast, Pour Pricey, Merge Mini" — earliest finish, highest value/weight density, do minimum frequencies.