Greedy — exchange argument proof technique: Question bank

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

Is page par use kiya gaya notation (pehle padho)

Definition Har symbol, seedhe shabdon mein

$G = (g_{1}, g_{2}, \dots, g_{n})$ — greedy algorithm jo choices karta hai unka sequence, order mein. $g_{i}$ greedy ki $i$ -vi choice hai.
$O = (o_{1}, o_{2}, \dots, o_{n})$ — koi bhi optimal solution, ordered sequence ke roop mein likha; $o_{i}$ uski $i$ -vi choice hai.
$O^{'}$ — wo solution jo aapko $O$ ke andar ek swap karne ke baad milta hai.
$OPT$ — best achievable objective value (jo optimal $O$ score karta hai).
$p_{k}$ — job $k$ ki processing time (length). $w_{k}$ — weighted problems mein uska weight (importance).
$C_{k}$ — job $k$ ki completion time: wo clock time jab wo finish hoti hai. $C_{a}, C_{b}$ do specific jobs $a, b$ ki completion times hain.
$f_{k}$ — interval problems mein activity $k$ ki finish time. $f_{g_{1}}$ = greedy ki pehli pick ki finish time, $f_{o_{1}}$ = optimal ki pehli pick ki finish time.
Huffman mein: $f (c)$ = symbol $c$ ki frequency; $depth (c)$ = code tree mein uski depth.

Neeche diagram is chain ko disagreements zero tak shrink hote dikhata hai.

Figure — Greedy — exchange argument proof technique

Recall Neeche reference kiye gaye tools ke statements (taaki aapko links chase na karni pade)

Smith's rule: weighted completion time $\sum_{k} w_{k} C_{k}$ minimize karne ke liye, jobs ko ratio $p_{k} / w_{k}$ ke increasing order mein schedule karo. Plain SPT (sort by $p_{k}$ ) special case hai $w_{k} = 1$ ke liye.
Huffman sibling lemma: kisi optimal prefix-code tree mein, do sabse kam frequency wale symbols $x, y$ maximum depth par sibling leaves hote hain. Do swaps ( $x \leftrightarrow a$ , $y \leftrightarrow b$ ) se prove hota hai jinka combined cost change $Δ \leq 0$ hota hai.
Exchange chain: upar wala sequence $O_{0} \to \dots \to G$ , har link pichle se no worse.

Shuru karne se pehle, har exchange proof ki teen obligations dhyan mein rakho — ye baar baar aate hain:

Recall Teen cheezein jo ek exchange proof mein hamesha establish karni hoti hain

(1) Swapped solution $O^{'}$ abhi bhi feasible hai (ek legal solution). (2) $O^{'}$ $O$ se no worse hai. (3) $O^{'}$ greedy se ek jagah zyada agree karta hai, isliye induction $G$ par terminate hoti hai. Ek bhi miss karo toh proof toot jaata hai.

True or false — justify karo

An exchange argument proves greedy is optimal by improving greedy's own output

False — aap

G

ko kabhi nahi chhugte; aap ek arbitrary optimal

O

lete ho aur usse

G

ki taraf edit karte ho, dikhate ho ki

G

O

se no worse hai.

If a single swap makes the objective strictly better, the original solution could not have been optimal

True — ye ek contradiction hai: ek optimal solution koi strictly-improving edit allow nahi karta, isliye jo configuration aapne swap ki (ek inversion) kisi bhi optimum mein nahi ho sakti.

A swap that leaves the objective exactly equal is useless for the proof

False — "equal" kaafi hai; ye dikhata hai ki koi optimum greedy se ek jagah zyada agree karta hai, jo activity selection jaise counting problems ko bas itna hi chahiye.

Exchange arguments aur greedy-stays-ahead same technique hain alag names ke saath

False — stays-ahead ek measure-based induction hai jo dikhata hai greedy kabhi peeche nahi; exchange physically

O

mein elements swap karta hai. Dono optimality prove karte hain lekin alag mechanisms se.

Exchange argument ke liye objective ka sum hona zaroori hai

False — ye zaroori hai ki ek local swap objective ka sirf ek bounded, computable piece change kare; sums ise aasaan banate hain lekin koi bhi objective jisme ye locality ho, kaam karta hai.

Ek baar dikhao ki ek swap hurt nahi karta, toh kaam ho gaya

False — aapko ye bhi argue karna hoga ki swaps terminate hote hain: har ek

G

ke saath disagreements ki sankhya kam karta hai, isliye finite swaps mein

G

tak pahunch jaate hain (wahi exchange chain hai).

Weighted completion time ke liye, processing time

p_{k}

se sort karna abhi bhi optimal hai

False — sahi order ratio

p_{k} / w_{k}

se hai (Smith's rule); akela

p_{k}

special case hai

w_{k} = 1

ka.

Huffman sibling lemma mein, single swap

x \leftrightarrow a

dikhana ki

\leq 0

proof finish karta hai

False — construction do swaps perform karta hai (

x \leftrightarrow a

aur

y \leftrightarrow b

); aapko dikhana hoga ki dono cost-change terms ka sum

Δ

\leq 0

hai.

Har greedy algorithm ko exchange argument se correct prove kiya ja sakta hai

False — kuch ko matroid theory ya DP-based comparison chahiye; exchange ordering/scheduling ke liye workhorse hai lekin universal nahi.

Agar greedy aur optimal har index par agree karte hain, toh koi swap zaroori nahi

True — wahi base case hai; koi first disagreement nahi, isliye

G = O

aur

cost (G) = OPT

trivially.

Error pakdo

"Maine do jobs swap kiye aur cost drop ho gayi, toh greedy optimal se better hai."

Error ye hai: optimal ko beat nahi kiya ja sakta, isliye iska matlab hai ki starting solution optimal nahi tha — swap prove karta hai ki kisi optimum mein inversion impossible hai, ye nahi ki greedy OPT ko beat karta hai.

"Maine koi bhi index choose kiya jahan

G

aur

O

differ karte hain aur wahan swap kiya."

Error ye hai: aapko first disagreement par swap karna hoga (sabse chhota

i

jahan

g_{i} \neq = o_{i}

) taaki already-matching prefix preserve ho; arbitrary index induction ko

G

ki taraf todh deta hai.

"Activity selection mein maine

o_{1}

g_{1}

se replace kiya aur bas check kiya ki count badhaa."

Error ye hai: feasibility bhoolna — pehle aapko argue karna hoga ki

f_{g_{1}} \leq f_{o_{1}}

taaki baad ki activities abhi bhi fit hon; tabhi equal count meaningful hai.

"SPT ke liye maine calculate kiya ki sirf

C_{a}

change hota hai jab adjacent

a, b

swap karte hain."

Error ye hai: dono

C_{a}

aur

C_{b}

change hote hain;

a

se pehle aur

b

ke baad wale jobs untouched rehte hain, lekin pair ki dono completion times shift hoti hain, aur difference

p_{a} - p_{b}

dono se aata hai.

"Swap ne swap kiye pair se door ke jobs bhi change kar diye, isliye maine poora schedule recompute kiya."

Error (ulta mistake): adjacent swap ke liye, pair ke bahar ke jobs ke completion times identical rehte hain; sab kuch recompute karna wasted work hai aur clean

p_{a} - p_{b}

result chhupa deta hai.

"Greedy har step par locally optimal hai, isliye globally bhi optimal hona chahiye."

Error: local ≠ global;

{1, 3, 4}

6

banane mein coin change greedy ko deta hai

4 + 1 + 1

(3 coins) vs optimal

3 + 3

(2). Sirf ek contradiction/exchange proof correctness certify karta hai.

"Mera exchange proof dikhata hai ki

O^{'}

no worse hai, toh kaam ho gaya — main

O^{'}

legal hai ye check skip karunga."

Error: ek "no worse" solution jo constraints violate karta hai kuch prove nahi karta; feasibility ek alag, mandatory obligation hai.

"Huffman mein maine assume kiya ki

a, b

sabse chhoti-frequency wale leaves hain."

Error:

x, y

sabse chhoti-frequency wale symbols hain;

a, b

sabse gehre sibling leaves hain. Ye generally alag hote hain, aur poora lemma inhe relate karne ke baare mein hai.

Why questions

O

mein

g_{i}

baad mein kahi appear kyon karna chahiye pehle swap karne se

Kyunki greedy koi bhi choice waste nahi karta, element

g_{i}

solution set ka hissa hai, isliye agar

O

optimal hai toh usme

g_{i}

kisi position

j > i

par hoga jise place

i

par swap kiya ja sake.

Shorter job pehle rakhne se

\sum C_{k}

kyun kam hota hai

Doosri jagah finish hone wali job apni completion time mein pehli job ki length "pay" karti hai; pehli job ko shorter banana us doubled contribution ko shrink karta hai, isliye sum

p_{a} - p_{b}

se drop hota hai.

Exchange chain

cost (G) \leq OPT

guarantee kyon karta hai

Chain

O_{0} \to \dots \to G

ki har link satisfy karti hai

cost (O_{i + 1}) \leq cost (O_{i})

; inequalities ko telescope karne se milta hai

cost (G) \leq cost (O) = OPT

Activity selection ke liye "earliest finish time" sahi greedy criterion kyon hai

Kyunki

f_{g_{1}} \leq f_{o_{1}}

guarantee karta hai ki

o_{1}

ke compatible koi bhi activity

g_{1}

ke saath bhi compatible hai, isliye swap feasibility preserve karta hai — criterion precisely isliye choose kiya jaata hai taaki obligation (1) automatic ho.

Weighted inversion swap cost ko

w_{b} p_{a} - w_{a} p_{b}

se kyun change karta hai

Adjacent

a, b

swap karne se

b

pehle aata hai (

w_{b} p_{a}

bachata hai) aur

a

baad mein (

w_{a} p_{b}

cost karta hai); net hai

w_{b} p_{a} - w_{a} p_{b}

, exactly non-negative jab

p_{a} / w_{a} \geq p_{b} / w_{b}

Hume sirf ek swap ke bajaye induction kyun chahiye

Ek swap sirf pehla disagreement fix karta hai; matching prefix par induction argument repeat karta hai jab tak poora solution

G

ke barabar na ho jaaye.

Example 1 mein objective decrease strict kyun hai lekin Example 2 mein sirf weak

SPT ek minimisation hai distinct lengths ke saath isliye inversion hataana cost strictly lower karta hai; activity selection count karta hai picks, isliye same-count replacement sirf "no worse" hai, strictly better nahi.

Edge cases

Agar do jobs ki processing time equal ho,

p_{a} = p_{b}

Swap se

cost

difference

p_{a} - p_{b} = 0

milta hai; dono orders optimal hain, isliye greedy ka tie-breaking harmless hai aur "no inversions" statement weakly abhi bhi hold karta hai.

Agar

O

pehle se hi

G

ke barabar ho

Toh koi first disagreement nahi; induction base case apply hota hai aur

cost (G) = cost (O) = OPT

trivially.

Agar selection problem mein saari activities mutually overlapping hon

Greedy exactly ek pick karta hai (earliest-finishing); optimum bhi ek hi hai, aur single replacement

o_{1} \to g_{1}

dikhata hai ki wo match karte hain.

Agar ek job ki length zero ho,

p_{k} = 0

Ye kisi bhi doubled term mein

0

contribute karta hai aur kabhi beneficial inversion create nahi karta; SPT use harmlessly pehle rakhta hai aur proof unaffected rehta hai.

Agar Huffman alphabet mein sirf ek symbol ho (single symbol)

Koi sibling pair nahi hai, isliye lemma mein swap setup hi nahi ho sakta; ye ek degenerate base case hai — ek single-symbol code depth

0

ka ek single leaf hai, trivially optimal, aur lemma tab tak apply nahi hota jab tak alphabet mein

\geq 2

symbols na hon.

Agar do sabse chhoti Huffman frequencies equal hon,

f (x) = f (y)

Δ

ke dono terms abhi bhi (non-negative)

\times

(non-positive)

\leq 0

evaluate hote hain; ties ka matlab sirf ye hai ki multiple optimal trees exist karte hain, sab swap se reachable.

Agar Huffman mein sabse chhote symbols already deepest siblings hon

Toh

x = a

y = b

, depth differences

0

hain, isliye

Δ = 0

aur koi swap zaroori nahi — base configuration already lemma satisfy karta hai.

Agar sirf ek job ho (ya ek activity)

Swap karne ke liye kuch nahi; greedy ki single choice trivially ek hi feasible solution hai, hence optimal.

Agar Smith's rule mein saare weights equal hon

Ratio

p_{k} / w_{k}

reduce ho jaata hai

p_{k}

par (ek constant times), plain SPT recover karta hai — unweighted case Smith's rule ka

w_{k} = 1

par specialisation hai.