Introduction to Algorithms, Lecture 15 November 5, 2001© 2001 by Charles E. Leiserson 1CS 445 Dynamic ProgrammingAlon EfratSlides courtesy of Charles Leiserson with small changes by Carola Wenk Dynamic programmingDesign technique, like divide-and-conquer.Example: Longest Common Subsequence (LCS)• Given two sequences x[1 . . m] and y[1 . . n], find a longest subsequence common to them both.x: A B C B D A By: B D C A B A“a” not “the”BCBA = LCS(x, y)   Brute-force LCS algorithmCheck every subsequence of x[1 . . m] to see if it is also a subsequence of y[1 . . n].Analysis• Checking = Θ(m+n) time per subsequence.• 2msubsequences of x (each bit-vector of length m determines a distinct subsequence of x).Worst-case running time = Θ((m+n)2m)= exponential time.Towards a better algorithmSimplification:1. Look at the length of a longest-common subsequence. 2. Extend the algorithm to find the LCS itself.Strategy: Consider prefixes of x and y.• Define c[i, j] = |LCS(x[1 . . i], y[1 . . j])|.• Then, c[m, n] = | LCS(x, y)|.Notation: Denote the length of a sequence sby |s|.Recursive formulationTheorem.c[i, j] =c[i–1, j–1] + 1 if x[i] = y[j],max{c[i–1, j], c[i, j–1]} otherwise.Let z[1 . . k] = LCS(x[1 . . i], y[1 . . j]), where c[i, j] = k. Then, z[k] = x[i], or else z could be extended. Thus, z[1 . . k–1] is CS of x[1 . . i–1] and y[1 . . j–1].Proof. First case to consider: x[i] = y[j]:1 2 i m1 2jnx:y:=Proof (continued case x[i] = y[j]:)Claim: z[1 . . k–1] = LCS(x[1 . . i–1], y[1 . . j–1]). Proof: Suppose w is a LCS of x[1 . . i–1] and y[1 . . j–1], and, | w | > k–1. Then, cut and paste: w || z[k] (w concatenated with z[k]) is a common subsequence of x[1 . . i] and y[1 . . j] with | w || z[k] | > k. Contradiction, proving the claim.Thus, c[i–1, j–1] = k–1, which implies that c[i, j] = c[i–1, j–1] + 1.Concluding this case.Introduction to Algorithms, Lecture 15 November 5, 2001© 2001 by Charles E. Leiserson 2Proof (cont). Case x[i] ≠≠≠≠ y[j]:Claim: in LCS(x[1 . . i], y[1 . . j]) it cannot be that both x[i] and y[j] participate. 1 2 i m1 2jnx:y:=Hence either LCS(x[1 . . i], y[1 . . j])= LCS(x[1 . . i], y[1 . . j-1])Or LCS(x[1 . . i], y[1 . . j])= LCS(x[1 . . i-1], y[1 . . j])whichever is smaller.Dynamic-programming hallmark #1Optimal substructureAn optimal solution to a problem (instance) contains optimal solutions to subproblems.If z = LCS(x, y), then any prefix of z is an LCS of a prefix of x and a prefix of y.Recursive algorithm for LCSLCS(x, y, i, j)if ( i==0 or j=0) return 0 if x[i] = y[ j]then return LCS(x, y, i–1, j–1) + 1else return max{ LCS(x, y, i–1, j), LCS(x, y, i, j–1)}To call the function LCS(x, y, m,n )Worst-case: x[i] ≠ y[ j], in which case the algorithm evaluates two subproblems, each with only one parameter decremented.same subproblembut we’re solving subproblems already solved!Recursion treem = 3, n = 4:3,42,41,43,33,22,31,3 2,2Height = m + n  work potentially 2m+nexponential.2,31,3 2,2m+nDynamic-programming hallmark #2Overlapping subproblemsA recursive solution contains a “small” number of distinct subproblems repeated many times.The number of distinct LCS subproblems for two strings of lengths m and n is only mn.Memoization algorithmMemoization: After computing a solution to a subproblem, store it in a table. Subsequent calls check the table to avoid redoing work.Time = Θ(mn) = constant work per table entry.Space = Θ(mn). LCS(x, y)for i=0 to m c[i, 0] = 0for j=0 to n c[0, j] = 0for i=1 to m for j=1 to n if (x[i] = y[j] )then c[i, j] ← c[ i–1, j–1] + 1else c[i, j] ← max{ c[ i–1, j], c[i, j–1] }Introduction to Algorithms, Lecture 15 November 5, 2001© 2001 by Charles E. Leiserson 30 0 0 0 00 0 1 1 10 0 01 1 10 0 1 1 1 2 2D20 0 1 2 2 2 2C 20 1 1 2 2 2 3A 30 1 2 2 3 3 3B 40 1 2 2 3 3ALCS: Dynamic-programming algorithmA B C B D BBA4 41 23 4 5 6 7Y=123456X=LCS(X,Y)=“BCBA”X=B D C A B AY=A B C B D A BReconstruction z=LCS(x,y)IDEA: Compute the table bottom-up. Fill z backward. 0 0 0 0 0 0 0 00 0 1 1 1 1 1 10 0 1 1 1 2 2D20 0 1 2 2 2 2C20 1 1 2 2 2 3A30 1 2 2 3 3 3B40 1 2 2 3 3AA B C B D BBA4 440 0BBA1CC2BB3AAD1A2D3B4LCS(x,y)=“BCBA”Observation: c[i;j]≥c[i-1;j] and c[i;j] ≥c[i;j-1]Proof Sketch: We use a longer prefix, so there are more chars to be match. x=B D C A B Ay=A B C B D A BLCS Reconstruction: Set i=m; j=n; k=c[i;j] While(k>0){if (c[i;j]>c[i-1;j] and c[i;j]>c[i;j-1] ) {z[k] = x[i] ;i--; j-- ; k-- ; }else /*c[i;j]=c[i-1;j] or c[i;j]=c[i-1;j]*/if (c[i;j]==c[i;j-1]) j— ; else i-- ; }1234561 23 4 5 6 7Reconstructing z=LCS(X,Y)Another idea – While filling c[], add arrows to each cell c[i,j] specifying which neighboring cell c[i,j] it got its value. • c[i,j].flag = “\ “ if c[i,,j]=c[ i-1;j-1]+1• c[i,j].flag = “↑ “ if c[i,,j]=c[i-1;j ]•c[i,j].flag = “←“ if c[i,,j]=c[i-1;j ]0 0 0 0 0 0 0 00 ↑0 1 ←1 1 1 1 10 ↑0 1 ←1←1 2 2D20 ↑0 ↑1 2 ←2←2 2C20 1 ↑1 2 ←2 2 3A30 ↑1 2 ←2 3 3 3B40 1 ↑2 ←2 ↑3 ←3AA B C B D BBA4 40A←4←0BB↑1CC↑2BB←3AAD1A2D3B4Another example of dynamic programming: Matrix Chain-Products• Review: Matrix Multiplication.– C = AB– A is d × e, B is e × f– O(def ) timeA CBd dfefeiji,j−==10],[],[],[ekjkBkiAjiCMatrix Chain-Products• Matrix Chain-Product:– Compute A = A0 A1…An-1– Aiis di× di+1– Problem: How to parenthesize?• Example 1. (A1A2 )( A3 A4 ) = A1 (A2( A3A4 )) = (A1 ( A2A3 )) A4 = A1(( A2A3 ) A4 )=…• Example 2– B is 3 × 100– C is 100 × 7– D is 7 × 5– (BC)D 3×100×7 + 7×5×5 = 2275 mults– B(CD) 3×100×5 + 100×7×5 = 5000 multsAn Enumeration Approach• Matrix Chain-Product Alg.:– Try all possible ways to parenthesize A=A0 A1…An-1– Calculate number of ops for each one– Pick the one that is best• Running time:– # of parenthesizations = # of binary trees with n nodes• Exponential!• Called the nthCatalan number – it is almost 4n.– This is a terrible algorithm!Introduction to