c Balaji Raghavachari 104 Algorithm Design and Analysis✬✫✩✪Greedy algorithms• Sometimes a problem may satisfy the optimalsubstructure property, and in addition a greedy choiceproperty, i.e., we may be able to find the right choicewithout trying out all possibilit i es.• In this case, we get a more efficient algorithm byfollowing the greedy choices.• For instances where all possibilities are tried, see choiceof k in slide 87. In this case, no greedy algorithm isknown for the problem.c Balaji Raghavachari 105 Algorithm Design and Analysis✬✫✩✪Activity selection problem• n activities S = {a1, a2, . . . , an} t ha t require resource R.Activity aineeds R during interval [si, fi).• Activities aiand ajare compatible if their intervals donot over l ap (i.e., si≥ fjor sj≥ fi).• Problem: find a largest cardinality subset of activitiesthat are mutually compatible with each other.• For t he example bel ow, {a3, a9, a11} forms a mutuallycompatible set. {a1, a4, a8, a11} a nd {a2, a4, a9, a11} arelargest m ut ua l ly compatible subsets of activities.i1 2 3 4 5 6 7 8 9 10 11si1 3 0 5 3 5 6 8 8 2 12fi4 5 6 7 8 9 10 11 12 13 14c Balaji Raghavachari 106 Algorithm Design and Analysis✬✫✩✪ASP example under different heuristicsStart: 1 3 0 5 3 5 6 8 8 2 12Finish: 4 5 6 7 8 9 10 11 12 13 14• Best solution: Gre edy strategy that selects earliestfinishing activity first: [1,4) [5,7) [8,11) [12,14)• Suboptimal algorithm: First-come first-served (FCFS):[0,6) [6, 10) [12,14)• Another gree dy optima l algorithm: Select lateststarting activity first: [12,14) [8,12) [5,7) [3,5)c Balaji Raghavachari 107 Algorithm Design and Analysis✬✫✩✪Optimal substructure property• Define Sij= {ak∈ S : fi≤ sk< fk≤ sj} (ac tivities thatstart after aifinishes and finish before ajstarts).• Let Aijbe an optimal solution (ma ximum cardinalitysubset of mutually compat ible activ i ties) of Sij.• Suppose ak∈ Aij. Then Aij= Aik∪ {ak} ∪ Akj.In other words, an optimal solution of Sijis c omposedof optimal solutions to subproblems.• Recursive solution: Base case: c(i, j) = 0 if Sij= φ.Otherwise,c(i, j) = maxi<k<jak∈Sij{c(i, k) + 1 + c(k, j)}• Dynamic program algorithm is easy (Ex. 16.1-1).c Balaji Raghavachari 108 Algorithm Design and Analysis✬✫✩✪Greedy choice property• Let ambe an ac tivity i n Sijwith earliest finish time.Then ther e is an optimal solution that includes am.• Why? Because in any optimal solution Aij, we canreplace the first act i vity akby am, without affectingcompatibility since, fm≤ fk.• Since Simis e mpty (because there are no activities inSijthat are compatible with amthat precede am), therecursive scheme runs in O(n) time.• Leads to the following iterative scheme: select theactivity that finishes first. Remove al l activiti e s that arenot compa tible with it. Repeat until there are noactivities left. R.T.=O(n) a fter activities are sorted bytheir finish ti mes.c Balaji Raghavachari 109 Algorithm Design and Analysis✬✫✩✪Details of greedy algorithm for ASPInput: Activities sorted by finish tim es: f1≤ f2≤ . . . ≤ fnRT = O(n) (if input is given unsorted, then O(n log n))freeAt ← 0 // Ti me at which resource is freefor i ← 1 to n doif si≥ f reeAt thenChoose activity aifreeAt ← fic Balaji Raghavachari 110 Algorithm Design and Analysis✬✫✩✪Greedy choice lemma• There exists an optimal solution that selects theactivity that finishes earliest (say, am).• Proof. Consider an optimal solution S. If am∈ S, thenS satisfies the lemma. Otherwise, let akbe the firstactivity in S. Since amfinishes earliest, we have fm≤ fk.Also, amand akare incompatible, since otherwiseS ∪ {am} is a bigger solution than S, contradicting itsoptimality. In addition, amis c ompa tible with allactivities of S except ak, because fm≤ fk≤ sifor a nyai∈ S − {ak}. Therefore, S′= S − {ak} ∪ {am} is acompatible set of activities, and |S′| = |S|. So, S′is alsoan optimal solution and S′includes am.c Balaji Raghavachari 111 Algorithm Design and Analysis✬✫✩✪Correctness of greedy algorithm for ASPProof by induction on n, the number of activities. If n = 0,there are no activitie s left and none are select ed. (I.H.) Letthe algorithm find an optimal solution for fewer than nactivities. Consider some n > 0. By greedy choice lemma,am, the earliest finishing activity is in some optimal solutionS. Any ac tivity that is not compatible with amis not in S.Our algorithm selects amand re moves it along with allactivities that are incompatible with it, yielding a set of(fewer than n) act i v ities. S − {am} is an optimal solution ofthe remaining activities. By the I.H., our algorithm finds asolution S′in it w i th |S′| = |S − {am}|. The solution outputby it is S′∪ {am}, which is the same cardinality as S.c Balaji Raghavachari 112 Algorithm Design and Analysis✬✫✩✪Huffman coding• Algorithm for compressing data (in communicat i onchannels, file s).• Example: consider a 100,000 character file with thefollowing distribution of i ts characters:Character A C T GFrequency (%) 50 25 10 15Fixed length code 00 01 10 11Variable length code 0 10 110 111• File le ngth (fixed length code): 100, 000 ∗ 2 = 200, 000.File le ngth (variable length code):100, 000 ∗ (0.5 ∗ 1 + 0.25 ∗ 2 + 0.1 ∗ 3 + 0.15 ∗ 3) = 175, 000.Space sa v ed: 12.5%c Balaji Raghavachari 113 Algorithm Design and Analysis✬✫✩✪The problem• Input: An alphabet C and a frequency function f (eachcharacter c ∈ C occurs with frequency f (c)).• Output: A prefix code for C that minimizes totallength of the file:– A code maps ea ch c ∈ C to a binary string.– A prefix code is a code in which no codeword is aprefix of another codeword.– A prefix code is easy to decode and requires noboundary markers between characters.– A prefix code can be represented by a binary tree inwhich each leaf corresponds to a letter in C.c Balaji Raghavachari 114 Algorithm Design and Analysis✬✫✩✪ExampleCharacter A C T G B(T)Frequency (%) 50 25 10 15Fixed length code 00 01 10 11 2Variable length code 0 10 110 111 1.75B(T ) =Xc∈Cf(c)dT(c).25100T : 10G : 15A : 50G : 15T : 10C : 25A : 5050100C : 252575010011010101c Balaji Raghavachari 115 Algorithm Design and Analysis✬✫✩✪Huffman coding algorithm• If there are only 2 letters, assign them codes 0 and 1.• Otherwise, find two least frequent
View Full Document
Unlocking...