c Balaji Raghavachari 104 Algorithm Design and Analysis Sometimes a problem may satisfy the optimal substructure property and in addition a greedy choice property i e we may be able to find the right choice without trying out all possibilities Algorithm Design and Analysis Activity selection problem For the example below a3 a9 a11 forms a mutually compatible set a1 a4 a8 a11 and a2 a4 a9 a11 are largest mutually compatible subsets of activities Algorithm Design and Analysis i 1 2 3 4 5 6 7 8 9 10 11 si 1 3 0 5 3 5 6 8 8 2 12 fi 4 5 6 7 8 9 10 11 12 13 14 c Balaji Raghavachari 107 Algorithm Design and Analysis Optimal substructure property Define Sij ak S fi sk fk sj activities that start after ai finishes and finish before aj starts ASP example under different heuristics Start 1 3 0 5 3 5 6 8 8 2 12 Finish 4 5 6 7 8 9 10 11 12 13 14 Let Aij be an optimal solution maximum cardinality subset of mutually compatible activities of Sij Best solution Greedy strategy that selects earliest finishing activity first 1 4 5 7 8 11 12 14 Suppose ak Aij Then Aij Aik ak Akj In other words an optimal solution of Sij is composed of optimal solutions to subproblems Suboptimal algorithm First come first served FCFS 0 6 6 10 12 14 Recursive solution Base case c i j 0 if Sij Otherwise Another greedy optimal algorithm Select latest starting activity first 12 14 8 12 5 7 3 5 Problem find a largest cardinality subset of activities that are mutually compatible with each other For instances where all possibilities are tried see choice of k in slide 87 In this case no greedy algorithm is known for the problem 106 105 Activities ai and aj are compatible if their intervals do not overlap i e si fj or sj fi In this case we get a more efficient algorithm by following the greedy choices c Balaji Raghavachari c Balaji Raghavachari n activities S a1 a2 an that require resource R Activity ai needs R during interval si fi Greedy algorithms c i j max c i k 1 c k j i k j ak Sij Dynamic program algorithm is easy Ex 16 1 1 c Balaji Raghavachari 108 Algorithm Design and Analysis Greedy choice property c Balaji Raghavachari 109 Algorithm Design and Analysis Let am be an activity in Sij with earliest finish time Then there is an optimal solution that includes am Details of greedy algorithm for ASP Why Because in any optimal solution Aij we can replace the first activity ak by am without affecting compatibility since fm fk Input Activities sorted by finish times f1 f2 fn RT O n if input is given unsorted then O n log n Since Sim is empty because there are no activities in Sij that are compatible with am that precede am the recursive scheme runs in O n time f reeAt 0 Time at which resource is free for i 1 to n do if si f reeAt then Choose activity ai f reeAt fi Leads to the following iterative scheme select the activity that finishes first Remove all activities that are not compatible with it Repeat until there are no activities left R T O n after activities are sorted by their finish times c Balaji Raghavachari 110 Algorithm Design and Analysis c Balaji Raghavachari Greedy choice lemma 111 Algorithm Design and Analysis Correctness of greedy algorithm for ASP There exists an optimal solution that selects the activity that finishes earliest say am Proof by induction on n the number of activities If n 0 there are no activities left and none are selected I H Let the algorithm find an optimal solution for fewer than n activities Consider some n 0 By greedy choice lemma am the earliest finishing activity is in some optimal solution S Any activity that is not compatible with am is not in S Our algorithm selects am and removes it along with all activities that are incompatible with it yielding a set of fewer than n activities S am is an optimal solution of the remaining activities By the I H our algorithm finds a solution S in it with S S am The solution output by it is S am which is the same cardinality as S Proof Consider an optimal solution S If am S then S satisfies the lemma Otherwise let ak be the first activity in S Since am finishes earliest we have fm fk Also am and ak are incompatible since otherwise S am is a bigger solution than S contradicting its optimality In addition am is compatible with all activities of S except ak because fm fk si for any ai S ak Therefore S S ak am is a compatible set of activities and S S So S is also an optimal solution and S includes am c Balaji Raghavachari 112 Algorithm Design and Analysis Huffman coding C T G Frequency 50 25 10 15 Fixed length code 00 01 10 11 0 10 110 111 Variable length code 114 Algorithm Design and Analysis Example Character A C T G Frequency 50 25 10 15 Fixed length code 00 01 10 11 2 0 10 110 111 1 75 Variable length code B T X Output A prefix code for C that minimizes total length of the file A prefix code is easy to decode and requires no boundary markers between characters A prefix code can be represented by a binary tree in which each leaf corresponds to a letter in C 0 75 A 50 1 C 25 0 25 T 10 0 1 G 15 Algorithm Design and Analysis Otherwise find two least frequent characters x and y Replace x and y by a new character z with f z f x f y Solve the problem recursively 1 A 50 0 50 Replace leaf node for z by internal node with leaves x and y as its children 1 C 25 0 115 If there are only 2 letters assign them codes 0 and 1 100 1 c Balaji Raghavachari Huffman coding algorithm f c dT c 100 B T c C 0 A prefix code is a code in which no codeword is a prefix of another codeword c Balaji Raghavachari Algorithm Design and Analysis A code maps each c C to a binary string File length fixed length code 100 000 2 200 000 File length variable length code 100 000 0 5 1 0 25 2 0 1 3 0 15 3 175 000 Space saved 12 5 113 Input An alphabet C and a frequency function f each character c C occurs with frequency f c Example consider a 100 000 character file with the following distribution of its characters A c Balaji Raghavachari The problem Algorithm for compressing data in communication channels files Character T 10 25 1 G 15 c Balaji Raghavachari 116 Algorithm Design and Analysis c Balaji Raghavachari 117 Algorithm Design …
View Full Document
Unlocking...