CS6363 Design and Analysis of Computer Algorithms Prof Sergey Bereg Greedy Algorithms Chapter 16 1 Activity selection problem We are given n activities a1 an where i th activity ai si fi starts at time si and finishes at time fi They require the same resource for example one lecture hall Two activities are ai and aj are compatible if si fi sj fj The activity selection problem ASP is to select a maximum size subset of mutually compatible activities 1 1 Activity Selection with Dynamic Programming We want to find optimal substructure of an optimal selection If ai is selected then there are 2 subproblems a problem with activities ak such that fk si and a problem with activities ak such that sk fi In general we have a subproblem of the following type Sij ak fi sk fk sj We add two fictitious activities a0 0 0 and sn 1 Suppose that activities are sorted by finish time f0 f1 f2 fn 1 Let c i j be the solution of ASP for Sij the maximum size of compatible activities in Sij Then 0 if Sij c i j max c i k c k j 1 if Sij 6 i k j ak Sij Then the maximum number of compatible activities is c 0 n 1 This is similar to matrix chain multiplication and the running time is the same O n3 1 2 Activity Selection with Greedy Approach Greedy choice Select an activity with minimum fi Remove it and incompatible activities Continue until no more activities left This can be implemented with a recursive algorithm R ECURSIVE ACTIVITY S ELECTOR s f i Input s 1 n is the array of start times f 1 n is the array of finish times Activities are sorted by finish time i is the activity selected previously 1 m i 1 2 while m n and sm fi Find the first activity in Si n 1 3 m m 1 4 if m n then 5 return am R ECURSIVE ACTIVITY S ELECTOR s f m 6 else return 1 Call R ECURSIVE ACTIVITY S ELECTOR s f 0 first time The running time is O n assuming that the activities are sorted by finish time We will prove that the algorithm finds an optimal schedule Theorem Consider any nonempty subproblem Sij and let am be the activity in Sij with the earliest finish time fm min fk ak Sij Then 1 Activity am is used in some optimal solution for Sij 2 The subproblem Sim is empty so choosing am leaves only one subproblem Smj Proof 2 Suppose that there is ak Sim Then fk sm fm and fk fm Contradiction with the choice of am 1 Let Aij be an optimal solution for Sij We sort the activities of Aij by finish time Let ak be the first activity in Aij If ak am then we are done Otherwise construct A0ij Aij ak am The activities in A0ij are compatible The recursive algorithm can be converted to an iterative one G REEDY ACTIVITY S ELECTOR s f Input s 1 n is the array of start times f 1 n is the array of finish times Activities are sorted by finish time 1 n length s 2 A a1 3 i 1 4 for m 2 to n 5 if s m f i then 6 A A am 7 i m 8 return A Its running time is O n Greedy Strategy 1 Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve 2 Prove that there is always an optimal solution to the original problem that makes the greedy choice so that the greedy choice is always safe 3 Show that if we combine the greedy choice and an optimal solution to the subproblem we arrive at an optimal solution to the original problem 2 Knapsack Problem There are n items ith item is worth vi dollars and weights wi pounds where vi and wi are integers Select items to put in knapsack with total weight W so that total value is maximized 0 1 knapsack problem each item must either be taken or left behind Fractional knapsack problem fractions of items are allowed i 1 2 3 wi 10 20 30 Consider an example with W 50 and 3 items vi 60 100 120 value per pound 6 5 4 2 Greedy choice take an item with maximum value per pound Greedy algorithm takes item 1 and then item 2 Total value 160 But the optimal solution is to take items 2 and 3 Total value 220 So greedy strategy doesn t work for 0 1 knapsack problem The fractional knapsack problem can be solved by the greedy algorithm I the above exemple it takes item 1 item 2 and 2 3 of item 3 Total weight 50 Total value 240 which is optimal 3 Huffman code We want to compress a file by encoding characters with binary codes One idea is the fixed length code Example a 00 b 01 c 11 Then acb 001101 Decode 010011 Variable length code Example a 0 b 10 c 11 Then acb 01110 Decode 010100 A binary sequence can be decoded if no codeword is a prefix of another codeword We call such code a prefix code It can be represented by a binary tree 0 1 0 d a 10 b 011 c 11 d 00 e 010 Encode ace Decode 0100010 1 1 0 0 1 e b c a Optimal code problem Given an alphabet C of n characters and frequency of each character find optimal prefix code so that the compressed file has minimum length Huffman algorithm constructs the optimal tree T The characters are the leaves of T Greedy choice select two vertices x and y of lowest frequency and replace them by a vertex z so that x and y are the children of z and the frequency of z is the sum of frequencies of x and y z y x Example character frequency a 45 b 13 c 12 1 45 a 13 b 12 c 16 d 2 45 a 13 b 12 c 16 d d 16 9 e y x e 9 f 5 5 f 4 45 a 25 b e 25 b 14 16 d c e f 100 f 5 6 3 d c 14 e 45 a 30 a b f c d e 3 f Huffman s algorithm H UFFMAN C 1 n C 2 Q C Q is the min priority queue 3 for i 1 to n 1 4 allocate a new node z 5 lef t z x E XTRACT M IN Q 6 right z y E XTRACT M IN Q 7 f z f x f y 8 I NSERT Q z 9 return E XTRACT M IN Q return the root of the tree Using a binary min heap the initialization in line 2 takes O n time Every E XTRACT M IN and I NSERT takes O lg n time Total time is …
View Full Document
Unlocking...