COEN 179 Lecture Notes - Lecture 21: Computational Complexity Theory, Dynamic Programming, Yottabyte
30 May 2020
School
Department
Course
Professor
Document Summary
Coen 179 lecture 21 longest common subsequence notes. Lcs of x and y have length 4, e. g. bdab and bcba. How to decrease instance size of lcs: look at the last letters of x, y: = xo . 2 cases : xna f-ims or xna ! We claim: there is a solution that includes both. Suppose there is a lcs that includes neither. Then c + a" is a larger subsequence of x, y contradiction. Ym -i must be included in any lcs of x, y. Then at least once must be excluded in any lcs of x, y. We may remove this letter and still get the same answer. We don"t know so try both and keep rest. Lcscxco . then k yms , n - 13,46 . m -it ) { go. co us (x. co . n -if it co . m -d) In general, subproblems correspond to finding lcs(prefix(x), prefix(y))
