c Balaji Raghavachari 84 Algorithm Design and Analysis DP for ASP Cij version RT O n3 for l 2 to n 2 do chain length for i 0 to n l 2 do j l i 1 because l j i 1 q 0 for k i 1 to j 1 do if fi sk and fk sj then q max q Pk DC i k DC k j DC i j q return DC Final solution DC 0 n 1 Note An O n2 DP can be derived by choosing ak to be last activity in Opt So Ckj is dropped from recurrence In this case only i 0 needs to be solved Try to work out the remaining details on your own c Balaji Raghavachari 86 Algorithm Design and Analysis MCM problem formulation c Balaji Raghavachari 85 Algorithm Design and Analysis Matrix chain multiplication problem Given a chain of compatible matrices A1 A2 An what is the best way to compute the product Recall that matrix multiplication is associative Assume that simple algorithm is used for matrix product A p q B q r takes O pqr operations For example consider A1 10 20 A2 20 50 A3 50 1 A12 10 50 A1 A2 takes 10 20 50 10 000 ops A12 A3 takes 10 50 1 500 ops A1 A2 A3 takes 10 000 500 10 500 ops A23 20 1 A2 A3 takes 20 50 1 1 000 ops A1 A23 takes 10 20 1 200 ops A1 A2 A3 takes 1 000 200 1 200 ops Input an array of dimensions p0 p1 pn represents problem A1 p0 p1 A2 p1 p2 An pn 1 pn c Balaji Raghavachari 87 Algorithm Design and Analysis DAC solution for MCM and towards DP solution Recursive solution Base case m i i 0 for any i Otherwise if i j Output Minimum number of operations needed to multiply above matrix product m i j min m i k m k 1 j pi 1 pk pj i k j 1 Same subproblem is solved many times R T is 2n Let m i j represent minimum number of operations needed to multiply sequence Ai Aj Subproblems that arise m i j for 1 i j n Optimal substructure if the product is split into two Ai Ak and Ak 1 Aj then each sub sequence should be multiplied using minimum number of operations m i k and m k 1 j operations respectively yielding matrices Ai k pi 1 pk and Ak 1 j pk pj Order of solving problems increasing values of j i increasing chain length Question what value of k should we use Running time is O n3 see DP Storage for solutions array M 1 n 1 n Store the value output by m i j in M i j c Balaji Raghavachari 88 Algorithm Design and Analysis Correctness of MCM recurrence c Balaji Raghavachari 90 MCM example Input 1 7 3 5 1 p0 p1 p2 p3 p4 1 7 3 5 1 M 1 2 M 1 1 M 2 2 p0 p1 p2 21 M 2 3 M 2 2 M 3 3 p1 p2 p3 105 M 3 4 M 3 3 M 4 4 p2 p3 p4 15 M 1 1 M 2 3 p p p 0 1 3 min M 1 2 M 3 3 p0 p2 p3 M 1 3 M 2 4 Algorithm Design and Analysis min 0 105 35 21 0 15 36 M 2 2 M 3 4 p p p 1 2 4 min M 2 3 M 4 4 p1 p3 p4 min 0 15 21 105 0 35 36 c Balaji Raghavachari 89 Algorithm Design and Analysis DP code for MCM Proof by induction on chain length l j i 1 If l 1 then i j There is only one matrix and the number of operations is 0 Let the formulation be correct for all values smaller than l Consider some l 1 We need to find how many operations are needed to compute Ai Aj Let an optimal algorithm split this chain into Ai Ak Ak 1 Aj Since the two chains involved are smaller than l the number of operations needed to multiply the 2 chains are m i k and m k 1 j We have to finally multiply two matrices whose dimensions are pi 1 pk and pk pj This takes pi 1 pk pj operations So the number of operations is m i k m k 1 j pi 1 pk pj Since we consider k k in our recurrence m i j is this value for i 1 to n do M i i 0 for l 2 to n do l chain length for i 1 to n l 1 do j i l 1 M i j for k i to j 1 do q M i k M k 1 j p i 1 p k p j if M i j q then M i j q S i j k return M S c Balaji Raghavachari M 1 4 91 Algorithm Design and Analysis M 1 1 M 2 4 p0 p1 p4 min M 1 2 M 3 4 p0 p2 p4 M 1 3 M 4 4 p0 p3 p4 min 0 36 7 21 15 3 36 0 5 39 Matrix M 1 2 3 4 i j 1 0 21 36 39 1 0 105 36 2 0 15 3 0 4 3 4 Matrix s i j 2 Optimal solution A1 A2 A3 A4 1 2 3 4 2 2 2 c Balaji Raghavachari 92 Algorithm Design and Analysis c Balaji Raghavachari 93 Algorithm Design and Analysis Longest common subsequence problem LCS Optimal substructure of LCS A sequence Z hz1 z2 zk i is a subsequence of X hx1 x2 xm i if there exists a strictly increasing index sequence hi1 i2 ik i such that for all j 1 2 k we have xij zj Let Z hz1 z2 zk i be an LCS of X hx1 x2 xm i and Y hy1 y2 yn i Let Zi hz1 z2 zi i 1 If xm yn then zk xm yn and Zk 1 is an LCS of Xm 1 and Yn 1 For example Z hA C A Ci is a subsequence of X hG A C T A G A G C Ai with corresponding index sequence h2 3 5 9i or h2 3 7 9i 2 If xm 6 yn then zk 6 xm implies that Z is an LCS of Xm 1 and Y LCS problem Given two sequences X hx1 x2 xm i and Y hy1 y2 yn i find a maximum length sequence Z that is a subsequence of both X and Y c Balaji Raghavachari 94 Algorithm Design and Analysis 3 If xm 6 yn then zk 6 yn implies that Z is an LCS of X and Yn 1 Recursive solution for LCS c Balaji Raghavachari 95 Algorithm Design and Analysis Correctness of LCS recurrence Proof by induction on i j If i 0 …
View Full Document
Unlocking...