Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 15 Prof charles e. leiserson
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 15 Prof. Charles E. Leiserson
Dynamic programming Design technique, like divide-and-conquer Example: Longest Common Subsequence (LCs) Given two sequences x[l.. m] and yll.n], find a longest subsequence common to them both a' not the 2 :A CB DA B BCBA :B D C A B A LCS(, y) functional notation but not a function c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.2
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.2 Dynamic programming Design 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 B y:B D C A B A “a” not “the” BCBA = LCS(x, y) functional notation, but not a function
Brute-force LCS algorithm Check every subsequence of[1. m to see if it is also a subsequence of[l Analysis Checking =O(n) time per subsequence 2m subsequences of x(each bit-vector of length m determines a distinct subsequence OIX Worst-case running time=O(n2m exponential time c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.3
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.3 Brute-force LCS algorithm Check every subsequence of x[1 . . m] to see if it is also a subsequence of y[1 . . n]. Analysis • Checking = O(n) time per subsequence. • 2m subsequences of x (each bit-vector of length m determines a distinct subsequence of x). Worst-case running time = O(n2m) = exponential time
Towards a better algorithm Simplification 1. Look at the length of a longest-common subsequence 2. Extend the algorithm to find the lcs itself. Notation: Denote the length of a sequence s Strategy: Consider prefixes of x and y Define ci,j=LCs([1.i,yll.i Then, cm, n]=LCS(x, y) c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.4
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.4 Towards a better algorithm Simplification: 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 s by |s|
Recursive formulation Theorem c门=c+1=1+1 ifx=yl] max c[i-1,1, c[i,j-1]) otherwise Proof. Case x[=yU小 X y etz.k=LCS(x[.il,yll.D, where ci,jI k. Then, =k=xi, or else z could be extended Thus, zll. k-l is Cs ofx. i-1 and yll.j-11 c 2001 by Charles E Leiserson Introduction to Agorithms Day 26 L15.5
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 26 L15.5 Recursive formulation Theorem. 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. Case x[i] = y[j]: L 1 2 i m L 1 2 j n x: y: =