Design and Analysis of Algorithms - GitHub Pages

1 Design and Analysis of AlgorithmsGreedy Algorithms1 Introduction of Greedy Algorithm2 Interval Scheduling3 Optimal Loading4 Scheduling to Minimizing Lateness5 Fractional Knapsack Problem6 Greedy Algorithm Does Not Work (not teach in class)1 / 58 Outline1 Introduction of Greedy Algorithm2 Interval Scheduling3 Optimal Loading4 Scheduling to Minimizing Lateness5 Fractional Knapsack Problem6 Greedy Algorithm Does Not Work (not teach in class)2 / 58 MotivationA game like chess can be won only bythinking aheada player who is foucsed entirely on immediate advanatges iseasy to in many other games, such as Scrabbleit s fine to make whichever move seems best at the momentand not worrying too much about future sort of myopic behavior is easy and convinient, making it anattractive algorithmic strategy3 / 58 MotivationA game like chess can be won only bythinking aheada player who is foucsed entirely on immediate advanatges iseasy to in many other games, such as Scrabbleit s fine to make whichever move seems best at the momentand not worrying too much about future sort of myopic behavior is easy and convinient, making it anattractive algorithmic strategy3 / 58 Greedy AlgorithmGreedy algorithm works: proof of correctnessInterval scheduling: induction on stepOptimal loading: induction on input sizeScheduling to minimum lateness: exchange argumentGreedy algorithm does not work.

2 Find a counter-exampleCoin changing problem4 / 58 Outline1 Introduction of Greedy Algorithm2 Interval Scheduling3 Optimal Loading4 Scheduling to Minimizing Lateness5 Fractional Knapsack Problem6 Greedy Algorithm Does Not Work (not teach in class)5 / 58 Interval {1,2, .. , n}is a set ofnjobs, jobistarts atsiandfinishes jobsiandjarecompatibleif they don t overlaps:si fjorsj fiGoal:find maximum subset of mutually compatible {2,5,8}6 / 58 Interval {1,2, .. , n}is a set ofnjobs, jobistarts atsiandfinishes jobsiandjarecompatibleif they don t overlaps:si fjorsj fiGoal:find maximum subset of mutually compatible {2,5,8}6 / 58 Example01234567891011time87654321job4and 7are not compatible7 / 58 Interval Scheduling: Greedy AlgorithmGreedy templateConsider jobs in somenatural order, then take each jobprovided it s compatible with the ones already strategy is short-sighted;the order might not beoptimalCandidate selection strategies[Earliest start time]Consider jobs in ascending order ofsi[Earliest finish time]Consider jobs in ascending order offi[Shortest interval]Consider jobs in ascending order offi si[Fewest conflicts]For each jobj, count the number ofconflicting jobscj.

3 Schedule in ascending order / 58 Interval Scheduling: Greedy AlgorithmGreedy templateConsider jobs in somenatural order, then take each jobprovided it s compatible with the ones already strategy is short-sighted;the order might not beoptimalCandidate selection strategies[Earliest start time]Consider jobs in ascending order ofsi[Earliest finish time]Consider jobs in ascending order offi[Shortest interval]Consider jobs in ascending order offi si[Fewest conflicts]For each jobj, count the number ofconflicting jobscj. Schedule in ascending order / 58 Counterexample for Earliest Start Time9 / 58 Counterexample for Shortest Interval10 / 58 Counterexample for Fewest Conflicts11 / 58 Greedy Algorithm: Earliest-Finish-Time-FirstAlgorithm 1:GreedySelect(S, si, fi, i [n])Output:maximum compatible subsetA S1:Sort jobs by finish time so thatf1 fn;2:n |S|;3:A ;4:fori 1tondo5:ifjobiis compatible withAthenA A {i};6:end7:returnA; to decide jobiis compatible withA? track of jobj that was last added toA.

4 Jobiiscompatible withAiffsi fj / 58 Demo of Earliest Finish Time {1,2, .. ,8} {2,4,8} (nlogn)Sorting by finish time: (nlogn)Compare to check compatible:O(n) algorithm always give the to prove it?13 / 58 Mathematic Induction for Greedy AlgorithmProof template for greedy algorithm1 Describe the correctness as a proposition about naturalnumbern, which claims greedy algorithm yields ,ncould be the algorithm steps or input the proposition is true for all natural basis: from the smallest instanceInduction steps: type 1 or type 2 induction14 / 58 Proposition for Earliest-Finish-Time-FirstLetSbe the job set of sizen,siandfiare the start time andfinish time, algorithmGreedySelect carries on thek-thstep, it choosekjobs(i1= 1, i2, .. , ik), which is exactly the firstkjobs the above proposition, k, the firstk-step choice isexactly the firstk-jobs of some maximum compatible subsetA,and will yieldAin at / 58 Mathematic Induction: Induction BasisLetS={1,2, .. , n}be the sorted job set:f1 fnInduction 1, proveAincludes job1 For an arbitrary maximum compatible subsetA, sort jobs inAinascending order according to the finish the first job inAisjandj = 1, then replace jobjwith job1,yieldingA :A = (A {j}) {1}1won t appear in(A {j}) |A|=|A |f1 fj replacement does not affect compatibility A isalso one of the maximum compatible subset ofAand.

5 A1..A 16 / 58 Mathematic Induction: Induction BasisLetS={1,2, .. , n}be the sorted job set:f1 fnInduction 1, proveAincludes job1 For an arbitrary maximum compatible subsetA, sort jobs inAinascending order according to the finish the first job inAisjandj = 1, then replace jobjwith job1,yieldingA :A = (A {j}) {1}1won t appear in(A {j}) |A|=|A |f1 fj replacement does not affect compatibility A isalso one of the maximum compatible subset ofAand ..A1..A 16 / 58 Mathematic Induction: Induction BasisLetS={1,2, .. , n}be the sorted job set:f1 fnInduction 1, proveAincludes job1 For an arbitrary maximum compatible subsetA, sort jobs inAinascending order according to the finish the first job inAisjandj = 1, then replace jobjwith job1,yieldingA :A = (A {j}) {1}1won t appear in(A {j}) |A|=|A |f1 fj replacement does not affect compatibility A isalso one of the maximum compatible subset ofAand ..A1..A 16 / 58 Mathematic Induction: Induction Step (1/2)Assume Proposition is true fork, prove it is also true fork+ 1(k+ 1)-step choice jobik+1and(i1.)

6 , ik)forms the firstk+ 1jobs of , algorithm choosesi1= 1, i2, .. , a maximum compatibleAthat containsi1, i2, .. , set of other elements inA(already sorted and notempty), andS be the set of compatible elements {i1, i2, .. , ik}.A={i1, i2, .. , ik} BS ={i|i S, si fk}i1, i2, .. , ikcompatible setS BincompatiblesetA17 / 58 Mathematic Induction: Induction Step (2/2)Consider two cases according to if jobik+1is the 1st job +1happens to the first job inB, then the desired resultimmediately follows,(k+ 1)-step choice still yields the partialsolution +1is not the first job inB, then we must haveik+1/ Bthe strategy choice of the greedy algorithm the finish timeofik+1must be earlier than the first job inBAt this point, we can replace the first job inBwith jobik+1,yieldingB . Obviously,|B |=|B|.{i1, i2, .. , ik} B =A Note that|A|=|A | A is still a maximum compatible setofS. This proves the induction , i2, .. , ikcandidatecompatiblesetS Aik+1 Bik+1B 18 / 58 Mathematic Induction: Induction Step (2/2)Consider two cases according to if jobik+1is the 1st job +1happens to the first job inB, then the desired resultimmediately follows,(k+ 1)-step choice still yields the partialsolution +1is not the first job inB, then we must haveik+1/ Bthe strategy choice of the greedy algorithm the finish timeofik+1must be earlier than the first job inBAt this point, we can replace the first job inBwith jobik+1,yieldingB.

7 Obviously,|B |=|B|.{i1, i2, .. , ik} B =A Note that|A|=|A | A is still a maximum compatible setofS. This proves the induction , i2, .. , ikcandidatecompatiblesetS Aik+1 Bik+1B 18 / 58 Mathematic Induction: Induction Step (2/2)Consider two cases according to if jobik+1is the 1st job +1happens to the first job inB, then the desired resultimmediately follows,(k+ 1)-step choice still yields the partialsolution +1is not the first job inB, then we must haveik+1/ Bthe strategy choice of the greedy algorithm the finish timeofik+1must be earlier than the first job inBAt this point, we can replace the first job inBwith jobik+1,yieldingB . Obviously,|B |=|B|.{i1, i2, .. , ik} B =A Note that|A|=|A | A is still a maximum compatible setofS. This proves the induction , i2, .. , ikcandidatecompatiblesetS Aik+1 Bik+1B 18 / 58 Outline1 Introduction of Greedy Algorithm2 Interval Scheduling3 Optimal Loading4 Scheduling to Minimizing Lateness5 Fractional Knapsack Problem6 Greedy Algorithm Does Not Work (not teach in class)19 / 58 Optimal Loading with weightwiand a boat withmaximum weight capacityW(no volume limit).

8 Loading plan that maximizes the number of containers onthe problem is a special case of0-1knapsack : containerboat: knapsackallvi= 120 / 58 ModelingLet(x1, x2, .. , xn)be the solution vector,xi {0,1}.xi= 1iffi-th container is on the boatGoal function:maxn i=1xiConstraint:n i=1wixi W, xi={0,1}, i [n]21 / 58 Algorithm DesignGreedy stepssorting container according to weight in ascending order, toensurew1 w2 wnloading the container from the smallest label, and stop untilloading next container will exceed the limit22 / 58 Proof of Correctness (Induction on Input Size)Lemma. input sizen, the algorithm yields the correct {1,2, .. , n}be the set of containers that has been sortedin ascending order, andw1 w2 when the input sizen= 1(there isonly one container), the greedy algorithm will yield the correctsolution. Obviously if the greedy algorithm yield optimalsolution for input sizen, it will also yield optimal solution forinput sizen+ / 58 Analysis of Greedy Algorithm: InterpretationS={1,2.}

9 , n+ 1},w1 wn+1ifW < w1, returnS={ }else remove container1, letW =W w1input size isn:S ={2,3, .. , n+ 1}optimal solutionI for(S , W )I {I } {1}proveIis the optimal solution for(S, W)24 / 58 Correctness Proof (1/2)Premise of induction:greedy strategy will yield optimal solution forinput sizen, consider input sizen+ 1S={1,2, .. , n+ 1}, w1 w2 wn+1 Premise of induction for input sizenS ={2, .. , n+ 1}, W =W w1 Greedy strategy yields optimal solutionI for(S , W ).LetI=I {1}.25 / 58 Correctness Proof (2/2) the optimal solution for(S, W).Proof by not, suppose there exists an optimalsolutionI for(S, W)and|I |>|I|.Assume I , since otherwise we can replace1withthe first container inI , also yield the optimal {1}forms a solution for(S , W )and|I {1}|>|I {1}|=|I |The existence ofI contradicts to the premise thatI is theoptimal solution for(S , W ).I1I {1}I 1I {1} I {1}I {1}not optimalcontradict!26 / 58 Summary0-1knapscak is anNP-hard problemoptimal loading is a variant of0-1knapscak problem, and canbe solevd using greedy algorithm e icientlyCorrectness on input size27 / 58 Outline1 Introduction of Greedy Algorithm2 Interval Scheduling3 Optimal Loading4 Scheduling to Minimizing Lateness5 Fractional Knapsack Problem6 Greedy Algorithm Does Not Work (not teach in class)28 / 58 Scheduling to Minimizing LatenessMinimizing lateness problem ( )A job setA, single resource processes one job at a time, alljobs come in at time0 Jobjrequirestjunits of processing time and is due at timedj(ddl).

10 Clearly,tj jobjstarts at timesj, it finishes at timefj=sj+ :S:A N,S(j) =sjis the start time of :Lateness function computes the lateness of job:L(j) = j=max{0, fj dj}=max{0, sj+tj dj}0sjfj=sj+tjdj29 / all jobs to minimizemaxlatenessmin{maxj A j}=min{maxj A{max{0,sj+tj dj}}} overlap i, j A, i =jsi+ti sj sj+tj si30 / 58 Example 1A12345S05131727T584103D1012151120L01216 10 Table:Sequential scheduling05131727301234531 / 58 Example 2A14235S05152327T510843D1011121520L04111 210 Table:Earliest-deadline first05152327301423532 / 58 Minimizing Lateness: Greedy AlgorithmsGreedy jobs according to some natural order.[Shortest processing time first]Schedule jobs in ascendingorder of processing 1= 0, 2= 11 10 = 1 2= 0, 1= 0(better)[Smallest slack]Schedule jobs in ascending order of slackdj 2= 10 10 = 0, 1= 11 2 = 9 1= 0, 2= 10 + 1 10 = 1(better)33 / 58 Minimizing Lateness: Earliest Deadline FirstAlgorithm 2:Schedule(A, T, D)1:sortnjobs inAso thatd1 d2 dn;2:t 0//from time 0;3:forj= 1tondo4:assign jobjto interval[t, t+tj];5:sj t;6:fj t+tj;7:t t+tj8:end9:returnintervals[s1, f1].