01:198:344 Lecture Notes - Lecture 6: Dynamic Programming
30 Nov 2017
School
Department
Course
Professor
Document Summary
Last lecture: learn divide and conquer technique, multiply 2 numbers a and b of n bits each. Divide and conquer takes o(nlog2 3): read how to do this for matrix multiplication in section 4. 2 in pages 75 83. This lecture: dynamic programming, de ne edit distance e(s, t ) between strings s and t to be the minimum character deletes, inserts and switches needed to convert s to t . Problem: given s and t , nd the edit distance e(s, t ): observe that e(s[i], t [j]) = e(s[i 1], t [j 1]) if s[i] = t [j] For i = 1, , n and for j = 1, , n, calculate e(s[i], t [j]) into an array . Then, the terms we need to calculate e(s[i], t [j]) will be available in the array: time: o(n2). For each (i, j), look at the formula above and.
