Activity selection problemActivity Selection with Dynamic ProgrammingActivity Selection with Greedy ApproachKnapsack ProblemHuffman codeCS6363: Design and Analysis of Computer Algorithms Prof. Sergey BeregGreedy AlgorithmsChapter 161 Activity selection problemWe are given n activities a1, . . . , anwhere i-th activity ai= [si, fi) starts at time siand finishes at time fi.They require the same resource (for example, one lecture hall). Two activities are aiand ajare compatible if[si, fi) ∩ [sj, fj) = ∅. The activity-selection problem (ASP) is to select a maximum size subset of mutuallycompatible activities.1.1 Activity Selection with Dynamic ProgrammingWe want to find optimal substructure of an optimal selection. If aiis selected then there are 2 subproblems:• a problem with activities aksuch that fk≤ si, and• a problem with activities aksuch that sk≥ fi.In general, we have a subproblem of the following typeSij= {ak| fi≤ sk< fk≤ sj}We add two fictitious activities a0= [0, 0) and sn+1= [∞, ∞) Suppose that activities are sorted byfinish time:f0≤ f1≤ f2· · · ≤ fn+1Let c[i, j] be the solution of ASP for Sij(the maximum size of compatible activities in Sij). Thenc[i, j] =(0 if Sij= ∅maxi<k<j,ak∈Sij{c[i, k] + c[k, j] + 1} if Sij6= ∅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 ApproachGreedy choice. Select an activity with minimum fi. Remove it and incompatible activities. Continue untilno more activities left.This can be implemented with a recursive algorithm:RECURSIVE-ACTIVITY-SELECTOR(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 + 12 while (m ≤ n and sm< fi) // Find the first activity in Si,n+13 m = m + 14 if m ≤ n then5 return {am}∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m)6 else return ∅1Call RECURSIVE-ACTIVITY-SELECTOR(s, f, 0) first time. The running time is O(n) (assuming thatthe activities are sorted by finish time). We will prove that the algorithm finds an optimal schedule.Theorem. Consider any nonempty subproblem Sij, and let ambe the activity in Sijwith the earliestfinish time:fm= min{fk| ak∈ Sij}.Then1. Activity amis used in some optimal solution for Sij.2. The subproblem Simis empty, so choosing amleaves only one subproblem Smj.Proof. 2. Suppose that there is ak∈ Sim. Then fk≤ sm< fmand fk< fm. Contradiction with thechoice of am.1. Let Aijbe an optimal solution for Sij. We sort the activities of Aijby finish time. Let akbe thefirst activity in Aij. If ak= amthen we are done. Otherwise construct A0ij= (Aij− {ak}) ∪ {am}. Theactivities in A0ijare compatible.The recursive algorithm can be converted to an iterative one:GREEDY-ACTIVITY-SELECTOR(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 = 14 for m = 2 to n5 if s[m] ≥ f [i] then6 A = A ∪ {am}7 i = m8 return AIts running time is O(n).Greedy Strategy1. Cast the optimization problem as one in which we make a choice and are left with one subproblem tosolve.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 atan optimal solution to the original problem.2 Knapsack ProblemThere are n items; ith item is worth vidollars and weights wipounds, where viand wiare integers. Selectitems 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.Consider an example with W = 50 and 3 itemsi 1 2 3wi10 20 30vi$60 $100 $120value per pound $6 $5 $42Greedy 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 takeitems 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 takesitem 1, item 2 and 2/3 of item 3. Total weight 50. Total value $240 which is optimal.3 Huffman codeWe 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 aprefix code. It can be represented by a binary tree.acbde00001111a = 10, b = 011, c = 11, d = 00, e = 010Encode ace.Decode 0100010.Optimal code problem. Given an alphabet C of n characters and frequency of each character, findoptimal 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 xand y are the children of z and the frequency of z is the sum of frequencies of x and y.xyxyzExample:character a b c d e ffrequency 45 13 12 16 9 5ea b c deff1445 13 12 1695ab c d4513 12 16bc25ef14d16a451)2)3)a45bc25efd304)5,6)bcefda1003Huffman’s algorithm:HUFFMAN(C)1 n = |C|2 Q = C // Q is the min-priority queue3 for i = 1 to n − 14 allocate a new node z5 lef t[z] = x =EXTRACT-MIN(Q)6 right[z] = y =EXTRACT-MIN(Q)7 f[z] = f[x] + f [y]8 INSERT (Q, z)9 return EXTRACT-MIN(Q) // return the root of the treeUsing a binary min-heap, the initialization in line 2 takes O(n) time. Every EXTRACT-MIN() andINSERT () takes O(lg n) time. Total time is O(n lg n).Theorem. Huffman’s algorithm produces an optimal code.Proof. Let B(T ) be the “cost” of a binary tree T (the length of encoded text in bits), i.e. B(T ) =Pc∈Cf(c)dT(c) where f(c) is the frequency of a character c and dT(c) is its depth in T .Part 1. If T is an optimal tree then it is full, i.e. a vertex u cannot be the only child of its parent v.uvu = vPart 2. Let a and b be two least frequent characters from C. Let T be an optimal tree with two siblingsa0and b0of maximum depth (they exist by Part 1). Make a tree T0by
View Full Document
Unlocking...