c Balaji Raghavachari 84 Algorithm Design and Analysis✬✫✩✪DP for ASP: Cijversion: RT = O(n3)for l ← 2 to n + 2 do // chain lengthfor i ← 0 to n − l + 2 doj ← l + i − 1 // because l = j − i + 1q ← 0for k ← i + 1 to j − 1 doif fi≤ skand fk≤ sjthenq ← max(q, Pk+ DC[i, k] + DC[k, j])DC[i, j] ← qreturn DC // Final solution: DC[0, n + 1]Note: An O(n2) DP c an be derived by choosing akto belast activity in Opt. So Ckjis dropped from recurrence. Inthis case, only i = 0 needs to be solved. Try to work out theremaining details on your own.c Balaji Raghavachari 85 Algorithm Design and Analysis✬✫✩✪Matrix chain multiplication problem• Given a cha in of compatible matrices A1, A2, . . . An,what is the b est way to compute the product?Recall that matrix multiplication is associative.• Assume that simple algorithm is used for matrixproduct (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· A2takes 10 ∗ 20 ∗ 50 = 10, 000 ops.A12· A3takes 10 ∗ 50 ∗ 1 = 500 ops.(A1· A2) · A3takes 10, 000 + 500 = 10, 500 ops.– A23[20 × 1] = A2· A3takes 20 ∗ 50 ∗ 1 = 1, 000 ops.A1· A23takes 10 ∗ 20 ∗ 1 = 200 ops.A1· (A2· A3) takes 1, 000 + 200 = 1, 200 ops.c Balaji Raghavachari 86 Algorithm Design and Analysis✬✫✩✪MCM problem formulation• Input: an array of dimensions p0, p1, . . . , pn(representsproblem A1[p0× p1] · A2[p1× p2] . . . An[pn−1× pn]).• Output: Minimum number of operations needed tomultiply above matrix product.• Let m(i, j) represent minimum numbe r of oper ationsneeded t o multiply sequence Ai. . . Aj.• Optimal substructure: if the product is split into two,Ai. . . Akand Ak+1. . . Aj, then each sub-sequence shouldbe multiplied using minimum number of operations(m(i, k) and m(k + 1, j) oper ations respectively), yiel dingmatrices Ai,k[pi−1× pk] and Ak+1,j[pk× pj].• Question: what value of k should we use?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,m(i, j) = mini≤k≤j−1{m(i, k) + m(k + 1, j) + pi−1pkpj}• Same subproblem is solved many times. R.T. is Ω(2n).• Subproblems that arise: m(i, j) for 1 ≤ i ≤ j ≤ n.• Storage for solutions: array M [1..n × 1..n].Store t he value output by m(i, j) in M [i, j].• Order of solving problems: increasing values of j − i(increasing chain length).• Running time is O(n3) (see DP).c Balaji Raghavachari 88 Algorithm Design and Analysis✬✫✩✪Correctness of MCM recurrenceProof by induction on chain length l = j − i + 1. If l = 1, theni = j. There is only one matrix, and the number ofoperations is 0. Let the formulation be correct for all valuessmaller than l. Consider some l > 1.We need to find how many operations are needed tocompute Ai..Aj. Let an optimal algorithm split this c ha i ninto ( Ai..Ak′)(Ak′+1..Aj). Since the two chains involved aresmaller than l, the numb er of operations needed to multiplythe 2 chains are m(i, k′) and m(k′+ 1, j). We have to finallymultiply two matric es, whose dimensions are pi−1× pk′andpk′× pj. This takes pi−1pk′pjoperations. So the number ofoperations is m(i, k′) + m(k′+ 1, j) + pi−1pk′pj. Since weconsider k = k′in our recurrence, m(i, j) is this value.c Balaji Raghavachari 89 Algorithm Design and Analysis✬✫✩✪DP code for MCMfor i ← 1 to n doM[i, i] ← 0for l ← 2 to n do // l: chain lengthfor i ← 1 to n − l + 1 doj ← i + l − 1M[i, j] ← ∞for k ← i to j − 1 doq ← M[i, k] + M[k + 1, j] + p[i − 1] ∗ p[k] ∗ p[j]if M [i, j] > q thenM[i, j] ← qS[i, j] ← kreturn M, Sc Balaji Raghavachari 90 Algorithm Design and Analysis✬✫✩✪MCM example• Input: {1, 7, 3, 5, 1}p0p1p2p3p41 7 3 5 1M[1, 2] = M[1, 1] + M [2, 2] + p0p1p2= 21.M[2, 3] = M[2, 2] + M [3, 3] + p1p2p3= 105.M[3, 4] = M[3, 3] + M [4, 4] + p2p3p4= 15.M[1, 3] = minM[1, 1] + M[2, 3] + p0p1p3,M[1, 2] + M[3, 3] + p0p2p3= min{0 + 105 + 35, 21 + 0 + 15} = 36.M[2, 4] = minM[2, 2] + M[3, 4] + p1p2p4,M[2, 3] + M[4, 4] + p1p3p4= min{0 + 15 + 21, 105 + 0 + 35} = 36.c Balaji Raghavachari 91 Algorithm Design and Analysis✬✫✩✪M[1, 4] = minM[1, 1] + M[2, 4] + p0p1p4,M[1, 2] + M[3, 4] + p0p2p4,M[1, 3] + M[4, 4] + p0p3p4= min{0 + 36 + 7, 21 + 15 + 3, 36 + 0 + 5} = 39.Matrix M Matrix si\j1 2 3 41 0 21 36 392 0 105 363 0 154 0i\j1 2 3 41 2 22 234Optimal solution: ((A1A2)(A3A4)).c Balaji Raghavachari 92 Algorithm Design and Analysis✬✫✩✪Longest common subsequence problem (LCS)• A sequence Z = hz1, z2, . . . , zki is a subsequence ofX = hx1, x2, . . . , xmi if ther e exists a strictly increasingindex sequence hi1, i2, . . . , iki such that for allj = 1, 2, . . . , k, we have xij= zj.• For example Z = hA, C, A, Ci i s a subsequence ofX = hG, A, C, T, A, G, A, G, C, Ai wi th corresponding indexsequence h2, 3, 5, 9i (or h2, 3, 7, 9i).• LCS problem: Given two sequences X = hx1, x2, . . . , xmiand Y = hy1, y2, . . . , yni, find a maximum length sequenceZ that is a subsequence of bot h X and Y .c Balaji Raghavachari 93 Algorithm Design and Analysis✬✫✩✪Optimal substructure of LCS• Let Z = hz1, z2, . . . , zki be an LCS of X = hx1, x2, . . . , xmiand Y = hy1, y2, . . . , yni. Let Zi= hz1, z2, . . . , zii.1. If xm= yn, then zk= xm= ynand Zk−1is an LCS ofXm−1and Yn−1.2. If xm6= yn, then zk6= xmimplies that Z is an LCS ofXm−1and Y .3. If xm6= yn, then zk6= ynimplies that Z is an LCS of Xand Yn−1.c Balaji Raghavachari 94 Algorithm Design and Analysis✬✫✩✪Recursive solution for LCS• Let c(i, j) denote the length of an LCS of Xiand Yj.• Base case: c(i, j) = 0 if i = 0 or j = 0. Otherw i se ,c(i, j) =c(i − 1, j − 1) + 1 if xi= yjmax{c(i, j − 1), c(i − 1, j)} if xi6= yj• Running time is exponential in m and n.• Subproblems that arise: c(i, j) for 0 ≤ i ≤ m, 0 ≤ j ≤ n.• Storage for solutions: array C[0..m × 0..n].Store t he value output …
View Full Document
Unlocking...