Greedy — exchange argument proof technique: Exercises

3.7.3 · D4 · Coding › Algorithm Paradigms › Greedy — exchange argument proof technique

Kisi bhi exercise se pehle, hum neeche use hone wale har symbol ko samjhenge:

Level 1 — Recognition

L1.1 — Kaunsi proof technique?

Tumhe dikhana hai: "greedy apne pehle $k$ picks mein se har ek ke baad optimal solution se kabhi peeche nahi hota." Kya yeh ek exchange/swap argument hai ya ek greedy-stays-ahead argument?

Recall Solution

Greedy-stays-ahead. Yeh ek measure track karta hai (tum $k$ picks ke baad kitna aage ho) aur dikhata hai ki greedy ka measure har $k$ par optimal ka measure dominate karta hai. Ek exchange argument instead optimal solution ko ek swap at a time physically edit karta hai. Contrast ke liye Greedy-stays-ahead proof technique dekho.

L1.2 — Inversion dhundho

Ek schedule jobs ko is order mein chalata hai (length brackets mein): $A (5), B (2), C (9), D (3)$ . SPT rule (shortest first) ke under, har adjacent inversion list karo.

Recall Solution

Adjacent pairs aur kya pehle wala lamba hai (SPT rule ke under inversion):

$A (5) \to B (2)$ : $5 > 2$ → inversion ✔
$B (2) \to C (9)$ : $2 < 9$ → theek hai
$C (9) \to D (3)$ : $9 > 3$ → inversion ✔

Do adjacent inversions: $(A, B)$ aur $(C, D)$ .

Level 2 — Application

L2.1 — Ek SPT swap, numbers ke saath

Do jobs time $t = 4$ par ek block ke roop mein start hoti hain: job $a$ mein $p_{a} = 7$ hai, job $b$ mein $p_{b} = 3$ hai, aur $O$ mein $a$ pehle chal raha hai $b$ se. $O$ mein $C_{a} + C_{b}$ compute karo, phir swapped schedule $O^{'}$ mein (jahan $b$ pehle ho), aur improvement do.

Recall Solution

$O$ mein ( $a$ phir $b$ ): $C_{a} = t + p_{a} = 4 + 7 = 11$ ; $C_{b} = t + p_{a} + p_{b} = 4 + 7 + 3 = 14$ . Sum $= 25$ . $O^{'}$ mein ( $b$ phir $a$ ): $C_{b} = t + p_{b} = 4 + 3 = 7$ ; $C_{a} = t + p_{b} + p_{a} = 4 + 3 + 7 = 14$ . Sum $= 21$ . Improvement $= 25 - 21 = 4 = p_{a} - p_{b} = 7 - 3$ . Formula $cost (O) - cost (O^{'}) = p_{a} - p_{b}$ se match karta hai.

Picture (Figure s01) "paid twice" idea ko visible banata hai. Ise aise padho: har row ek schedule hai, har block ki width uski processing time $p$ hai, aur red arrow us finish time par point karta hai jo dono $C$ -values ke andar count hoti hai (pehle job ki length dobara second job ki completion mein add hoti hai). Top row ( $O$ ) mein woh doubled length lamba red bar ka $p_{a} = 7$ hai; bottom row ( $O^{'}$ ) mein woh chhota green bar ka $p_{b} = 3$ hai. Toh figure geometrically dikhata hai kyun total exactly $p_{a} - p_{b}$ se girta hai: tum us length ko shrink karte ho jo twice charge hoti hai. Figure ke bina " $2 p_{a}$ vs $2 p_{b}$ " doubling sirf algebra hai; figure ke saath tum dekh sakte ho kaunsa bar doubled hai.

Figure — Greedy — exchange argument proof technique

L2.2 — Ek Smith's-rule swap

Weighted completion time $\sum w_{k} C_{k}$ . Adjacent jobs $a$ phir $b$ : $(p_{a}, w_{a}) = (6, 2)$ , $(p_{b}, w_{b}) = (4, 3)$ . Kya swap karna chahiye? Cost change $w_{b} p_{a} - w_{a} p_{b}$ compute karo aur interpret karo.

Recall Solution

Formula kahan se aata hai. Maano pair time $t$ par start hota hai (chahe pehle koi bhi job chale). Order $a$ -then- $b$ mein: $C_{a} = t + p_{a}$ aur $C_{b} = t + p_{a} + p_{b}$ , toh pair contribute karta hai $w_{a} (t + p_{a}) + w_{b} (t + p_{a} + p_{b})$ . Order $b$ -then- $a$ mein: contribution hai $w_{b} (t + p_{b}) + w_{a} (t + p_{b} + p_{a})$ . Subtract karne par, $t$ wale har term cancel ho jaate hain (dono jobs abhi bhi $t$ se pehle start nahi karti), bacha rehta hai $cost (a -first) - cost (b -first) = w_{b} p_{a} - w_{a} p_{b} .$ Isliye messy expression is clean cross-difference mein collapse hoti hai: yeh exactly mutual-waiting penalty ko isolate karta hai.

Plug in. $w_{b} p_{a} - w_{a} p_{b} = 3 \cdot 6 - 2 \cdot 4 = 18 - 8 = 10 > 0$ . Positive matlab current order ( $a$ phir $b$ ) zyada cost karta hai — swap help karta hai $10$ se. Equivalently, $p_{a} / w_{a} = 6/2 = 3$ aur $p_{b} / w_{b} = 4/3 \approx 1.33$ ; kyunki $3 > 1.33$ hai, job $a$ ka ratio bura hai aur usse baad mein jana chahiye. Yeh hai Smith's rule — weighted completion time.

Tie case: agar $p_{a} / w_{a} = p_{b} / w_{b}$ toh $w_{b} p_{a} - w_{a} p_{b} = 0$ — koi bhi order equally achha hai, toh ties arbitrarily break karo.

Level 3 — Analysis

L3.1 — Strict vs equal kyun?

SPT proof mein swap ek strict improvement deta hai, lekin activity-selection proof mein woh equal cost deta hai. Explain karo ki har problem ki kaunsi feature strict vs equal force karti hai, aur kyun dono phir bhi optimality prove karte hain.

Recall Solution

SPT ek sum of real quantities ( $\sum C_{k}$ ) minimise karta hai. Ek genuine inversion ( $p_{a} > p_{b}$ ) swap ko strictly $p_{a} - p_{b} > 0$ se sasta banata hai. Strictness humein contradiction se argue karne deta hai: ek optimal schedule mein inversion nahi ho sakta, warna hum use beat kar lete. (Ek tie par $p_{a} = p_{b}$ , change $0$ hota hai — inversion nahi, kuch fix karne ki zaroorat nahi.)
Activity selection activities count karta hai. $o_{1}$ ko earlier-finishing $g_{1}$ se replace karna count same rakhta hai (one-for-one), toh swap weakly no-worse hai. Yeh optimality preserve karta hai instead of improve karne ke, phir hum remainder par induct karte hain — dekho Activity Selection Problem.

Dono kaam karte hain kyunki exchange contract sirf "no worse" require karta hai. Strict improvement ek bonus hai (aur contradiction phrasing enable karta hai); equality swap chain $O \to O_{1} \to \dots \to G$ ke saath optimality carry karne ke liye kaafi hai.

L3.2 — Huffman: dono terms zaroori hain

Optimal tree cost hai $\sum_{c} f (c) d_{c}$ (frequency times depth). Hum $x \leftrightarrow a$ aur $y \leftrightarrow b$ swap karte hain. Given $f (x) = 1, f (a) = 4, d_{x} = 2, d_{a} = 5$ aur $f (y) = 2, f (b) = 3, d_{y} = 1, d_{b} = 5$ , har swap ka $Δ$ aur total compute karo. Confirm karo $Δ_{total} \leq 0$ .

Recall Solution

Har $Δ$ kahan se aata hai. Cost hai $\sum_{c} f (c) d_{c}$ (yahan $f (c)$ symbol ki frequency hai aur $d_{c}$ tree mein uski depth). Symbols $x$ aur $a$ ko swap karne ka matlab hai $x$ ab depth $d_{a}$ par baithega aur $a$ depth $d_{x}$ par; har doosra symbol apni depth rakhe ga, toh unke saare terms difference mein cancel ho jaate hain. Sirf do moved symbols survive karte hain: $Δ_{1} = [f (x) d_{a} + f (a) d_{x}] - [f (x) d_{x} + f (a) d_{a}] = (f (a) - f (x)) (d_{x} - d_{a}) .$ Woh factored form isliye swap ko sign karna easy banata hai: yeh frequency gap aur depth gap ka product hai. Same algebra $y, b$ ke saath $Δ_{2} = (f (b) - f (y)) (d_{y} - d_{b})$ deta hai.

Plug in. Pehla swap: $Δ_{1} = (f (a) - f (x)) (d_{x} - d_{a}) = (4 - 1) (2 - 5) = 3 \cdot (- 3) = - 9$ . Doosra swap: $Δ_{2} = (f (b) - f (y)) (d_{y} - d_{b}) = (3 - 2) (1 - 5) = 1 \cdot (- 4) = - 4$ . Total $Δ = - 9 + (- 4) = - 13 \leq 0$ . Cost strictly decrease hoti hai yahan. Har factor pattern: $(f (deep) - f (shallow-symbol)) \geq 0$ times $(d_{shallow-symbol} - d_{deep}) \leq 0$ non-positive product deta hai. Tie case: agar frequency gap $0$ ho (equal frequencies) ya depth gap $0$ ho, woh term exactly $0$ hai — phir bhi koi increase nahi. Dono ko sum karna mandatory hai — dekho Huffman Coding.

Level 4 — Synthesis

L4.1 — Full SPT exchange proof

Poora exchange argument likho ki SPT (shortest processing time first) $\sum_{k} C_{k}$ minimise karta hai. 5-step skeleton use karo.

Recall Solution

1. Setup. Maano $O$ koi bhi optimal schedule hai, $G$ SPT schedule hai. 2. First difference. Agar $O = G$ , done. Warna $O$ sorted order se differ karta hai, toh usme kam se kam ek adjacent inversion hai: jobs $a$ phir $b$ with $p_{a} > p_{b}$ . (Agar koi adjacent pair inverted na ho, toh poora order sorted hota = $G$ .) 3–4. Swap. Adjacent pair $a, b$ ko exchange karke $O^{'}$ banao. $a$ se pehle aur $b$ ke baad ka har job apna exact start time rakhe ga, toh sirf $C_{a}, C_{b}$ change hote hain — feasibility holds (abhi bhi ek time par ek job). 5. No worse. Maano $t$ job $a$ ka start time hai $O$ mein (equivalently, adjacent $a, b$ block ka start time, kyunki $b$ immediately $a$ ke baad chalta hai). $O$ mein: $C_{a} = t + p_{a}$ , $C_{b} = t + p_{a} + p_{b}$ , toh unka sum hai $2 t + 2 p_{a} + p_{b}$ . $O^{'}$ mein: $C_{b} = t + p_{b}$ , $C_{a} = t + p_{b} + p_{a}$ , sum $2 t + 2 p_{b} + p_{a}$ . Hence $cost (O) - cost (O^{'}) = (2 p_{a} + p_{b}) - (2 p_{b} + p_{a}) = p_{a} - p_{b} > 0.$ Toh $O^{'}$ strictly sasta hai — impossible agar $O$ optimal tha aur usme inversion tha. Isliye optimal mein koi inversion nahi, yaani yeh SPT $= G$ se sorted hai. Hence $G$ optimal hai. $■$ Tie case: agar $p_{a} = p_{b}$ toh difference $0$ hai — dono orders ka cost same hai, toh equal-length jobs kisi bhi order mein reh sakti hain aur SPT (ties arbitrarily break karke) phir bhi optimal hai. (Adjacency-only argument kaafi hai kyunki koi bhi inversion ek adjacent inversion imply karta hai — dekho L1.2.)

L4.2 — Full activity-selection first-step lemma

Prove karo: koi optimal solution $g_{1}$ include karta hai, woh activity jo globally sabse pehle khatam hoti hai.

Recall Solution

Is proof ke liye notation. Har activity $i$ ek interval $[s_{i}, f_{i})$ hai, jahan $s_{i}$ uska start time hai (jab shuru hoti hai) aur $f_{i}$ uska finish time hai (jab khatam hoti hai). (Yeh $f$ finish-time hai — Huffman exercise L3.2 mein use hone wale frequency $f (\cdot)$ se alag hai.) Setup. Maano $O = (o_{1}, o_{2}, \dots)$ optimal hai, uski activities finish time se sorted hain. Maano $g_{1}$ woh activity hai jiska finish time sab activities mein sabse chhota hai, toh $f_{g_{1}} \leq f_{o_{1}}$ . Swap. $o_{1}$ ko $g_{1}$ se replace karke $O^{'}$ banao, $o_{2}, o_{3}, \dots$ rakhte hue. Feasibility. $O$ mein, activity $o_{2}$ start hoti hai $s_{o_{2}} \geq f_{o_{1}}$ par (woh overlap nahi karti). Kyunki $f_{g_{1}} \leq f_{o_{1}} \leq s_{o_{2}}$ , activity $o_{2}$ abhi bhi $g_{1}$ khatam hone ke baad start hoti hai. $g_{1}$ vs $o_{2}$ : compatible. Baad ki sab activities already $o_{1}$ ke baad thi, hence $g_{1}$ ke baad bhi hain. Toh $O^{'}$ ek valid (pairwise non-overlapping) selection hai. No worse. $∣ O^{'} ∣ = ∣ O ∣$ (one for one swap), toh $O^{'}$ bhi optimal hai aur usme $g_{1}$ hai. Tie case: agar do activities globally sabse pehli finish time share karein, koi bhi $g_{1}$ ka kaam kar sakti hai; wahi $f_{g_{1}} \leq f_{o_{1}}$ argument hold karta hai, toh choice free hai. Induct karo $f_{g_{1}}$ ke baad start hone wali activities ke subproblem par: same lemma apply hota hai, toh greedy ka har pick ek optimum tak extendable hai. $■$

Level 5 — Mastery

L5.1 — Greedy key khud invent karo (deadline penalties)

$n$ unit-length jobs, sab time $0$ par available, har ek slot $1, 2, 3, \dots$ mein ek chale. Job $k$ ka weight $w_{k}$ hai aur, agar woh slot $C_{k}$ mein khatam ho, penalty pay karta hai $w_{k} \cdot C_{k}$ . Adjacent-swap analysis use karke, sahi sorting key derive karo aur prove karo.

Recall Solution

Is proof ke liye notation. Ek "slot" ek unit time interval hai; slot number $m$ mein rakha job $C = m$ par khatam hota hai. Do adjacent jobs $a, b$ consider karo jahan $O$ mein $a$ slot $m$ mein aur $b$ slot $m + 1$ mein chalta hai.

Swap change derive karo. Swap karne par $b$ slot $m$ mein aur $a$ slot $m + 1$ mein aata hai. Sirf ye do jobs slots change karti hain, toh baki saari penalties difference mein cancel ho jaati hain: $Δ = [order a, b w_{a} m + w_{b} (m + 1)] - [order b, a w_{b} m + w_{a} (m + 1)] .$ Expand karo: $m$ -terms dete hain $w_{a} m + w_{b} m - w_{b} m - w_{a} m = 0$ (slot index $m$ completely cancel ho jaata hai, kyunki dono jobs abhi bhi same do slots occupy karti hain), aur $+ 1$ terms dete hain $w_{b} - w_{a}$ . Toh $Δ = w_{b} - w_{a} .$

Key read off karo. Swap help karta hai (cost lower karta hai) jab $Δ < 0$ , yaani jab $w_{a} < w_{b}$ : ek lighter job jo ek heavier job se pehle baitha hai usse swap karna chahiye taaki heavier job pehle aa sake. Isliye greedy rule hai weight se sort karo, descending — sabse bada weight pehle.

Proof (exchange argument). Koi bhi optimal schedule $O$ lo. Agar $O$ kabhi ek lighter job ko immediately ek heavier job se pehle chalaye ( $w_{a} < w_{b}$ with $a$ before $b$ ), toh upar wala adjacent swap cost $w_{b} - w_{a} > 0$ se lower karta hai, jo optimality ko contradict karta hai. Hence optimal mein aisa koi inversion nahi hai, toh yeh descending weight $= G$ se sorted hai. Isliye $G$ optimal hai. $■$

Tie case: agar $w_{a} = w_{b}$ toh $Δ = 0$ — equal-weight jobs kisi bhi slot mein ho sakte hain; ties arbitrarily break karo. (Yeh Smith's rule hai sab $p_{k} = 1$ ke saath: ratio $p_{k} / w_{k} = 1/ w_{k}$ ascending $\Leftrightarrow$ weight descending.)

L5.2 — Exchange kab fail karta hai? (bridge to DP)

Coin change denominations ${1, 3, 4}$ se $6$ banane ke liye, greedy-by-largest kitne coins deta hai, aur true optimum kitne? Explain karo, ek sentence mein, kyun koi bhi adjacent-swap argument greedy ko yahan bacha nahi sakta — yeh connect karo is baat se ki hum Dynamic Programming par kyun escalate karte hain.

Recall Solution

Greedy-by-largest: $4 + 1 + 1 = 3$ coins. Optimum: $3 + 3 = 2$ coins. Greedy optimal nahi hai. Koi exchange argument kaam nahi karta kyunki problem mein exchange property nahi hai: ek single greedy coin ko doosre se swap karna monotonically improve nahi karta — optimum ${3, 3}$ greedy ki pehli choice ( $4$ ) ke saath koi coin share nahi karta, toh koi local swap chain $O \to \dots \to G$ nahi hai jo feasible aur no-worse rahe. Jab greedy/exchange (ya matroid) structure absent ho, tab hume DP ki overlapping-subproblem machinery chahiye.

Recall Self-test checklist

Mera har exchange proof objective state karta hai ::: haan — optimise hone wala number kisi bhi swap se pehle naam leta hai Main pehle disagreement par swap karta hoon aur matching prefix par induct karta hoon ::: haan Main $O^{'}$ ki feasibility check karta hoon, sirf uski cost nahi ::: haan Agar construction do swaps kare toh main dono $Δ$ terms sum karta hoon ::: haan Main jaanta hoon strict-improvement (contradiction) vs equal-cost (preserve) dono valid hain ::: haan Greedy key mein tie par swap change exactly $0$ hota hai, toh ties arbitrarily break hoti hain ::: haan