Lecture 10: Dynamic Programming

Lecture 10 Introduction 6.046J Spring 2015 Lecture 10: Dynamic Programming • Longest palindromic sequence • Optimal binary search tree • Alternating coin game DP notions 1. Characterize the structure of an optimal solution 2. Recursively define the value of an optimal solution based on optimal solutions of subproblems 3. Compute the value of an optimal solution in bottom-up fashion (recursion & memoization) 4. Construct an optimal solution from the computed information Longest Palindromic Sequence Definition: A palindrome is a string that is unchanged when reversed. Examples: radar, civic, t, bb, redder Given: A string X[1 · · · n], n ≥ 1 To find: Longest palindrome that is a subsequence Example: Given “c h a r a c t e r” output “c a r a c” Answer will be ≥ 1 in length Strategy L(i, j): length of longest palindromic subsequence of X[i · · · j] for i ≤ j. 1 Lecture 10 1 2 3 4 5 6 7 Introduction 6.046J Spring 2015 def L(i, j) : if i == j: return 1 if X[i] == X[j]: if i + 1 == j: return 2 else : return 2 + L(i + 1, j - 1) else : return max(L(i + 1, j), L(i, j - 1)) Exercise: compute the actual solution Analysis As written, program can run in exponential time: suppose all symbols X[i] are dis­ tinct. T (n) = running time on input of length n 1 n=1 T (n) = 2T (n − 1) n > 1 n−1 =2 Subproblems n = θ(n2 ) distinct subproblems: each is an (i, j) pair with 2 i < j. By solving each subproblem only once. running time reduces to But there are only θ(n2 ) · θ(1) = θ(n2 ) where θ(n2 ) is the number of subproblems and θ(1) is the time to solve each subproblem, given that smaller ones are solved. Memoize L(i, j), hash inputs to get output value, and lookup hash table to see if the subproblem is already solved, else recurse. Memoizing Vs. Iterating 1. Memoizing uses a dictionary for L(i, j) where value of L is looked up by using i, j as a key. Could just use a 2-D array here where null entries signify that the problem has not yet been solved. 2. Can solve subproblems in order of increasing j − i so smaller ones are solved first. 2 Lecture 10 6.046J Spring 2015 Introduction Optimal Binary Search Trees: CLRS 15.5 Given: keys K1 , K2 , · · · , Kn , K1 < K2 < · · · < Kn , WLOG Ki = i weights W1 , W2 , · · · , Wn Find: BST T that minimizes: n L Wi · (depthT (Ki ) + 1) i=1 Example: Wi = pi = probability of searching for Ki Then, we are minimizing expected search cost. (say we are representing an English → French dictionary and common words should have greater weight) Enumeration Exponentially many trees 2 1 n = 2 2 1 W1 + 2W2 3 3 n = 3 2 1 3W1 + 2W2 + W3 2W1 + W2 1 1 3 3 2 2W1 + 3W2 + W3 1 1 2 2 2W1 + W2 + 2W3 W1 + 3W2 + 2W3 Strategy W (i, j) = Wi + Wi+1 + · · · + Wj e(i, j) = cost of optimal BST on Ki , Ki+1 , · · · , Kj Want e(1, n) Greedy solution? Pick Kr in some greedy fashion, e.g., Wr is maximum. greedy doesn’t work, see example at the end of the notes. 3 2 3 W1 + 2W2 + 3W3 Lecture 10 Introduction 6.046J Spring 2015 Kr keys Kr+1,…, Kj e(r+1, j) keys Ki,…, Kr-1 e(i, r-1) DP Strategy: Guess all roots e(i, j) = ⎧ ⎨ Wi if i = j ⎩ min (e(i, r − 1) + e(r + 1, j) + W (i, j)) else i≤r≤j +W (i, j) accounts for Wr of root Kr as well as the increase in depth by 1 of all the other keys in the subtrees of Kr (DP tries all ways of making local choices and takes advantage of overlapping subproblems) Complexity: θ(n2 ) · θ(n) = θ(n3 ) where θ(n2 ) is the number of subproblems and θ(n) is the time per subproblem. Alternating Coin Game Row of n coins of values V1 , · · · , Vn , n is even. In each turn, a player selects either the first or last coin from the row, removes it permanently, and receives the value of the coin. Question Can the first player always win? Try: 4 42 39 17 25 6 Strategy V1 , V2 , · · · , Vn−1 , Vn 1. Compare V1 + V3 + · · · + Vn−1 against V2 + V4 + · · · + Vn and pick whichever is greater. 2. During the game only pick from the chosen subset (you will always be able to!) How to maximize the amount of money won assuming you move first? 4 Lecture 10 Introduction 6.046J Spring 2015 Optimal Strategy V (i, j): max value we can definitely win if it is our turn and only coins Vi , · · · , Vj remain. V (i, i) : just pick i. V (i, i + 1): pick the maximum of the two. V (i, i + 2), V (i, i + 3), · · · V (i, j) = max{(range becomes (i + 1, j)) + Vi , (range becomes (i, j − 1)) + Vj } Solution V (i + 1, j) subproblem with opponent picking we are guaranteed min{V (i + 1, j − 1), V (i + 2, j)} Where V (i+1, j−1) corresponds to opponent picking Vj and V (i+2, j) corresponds to opponent picking Vi+1 We have V (i, j) = max min V (i + 1, j − 1), V (i + 2, j) + Vi , min V (i, j − 2), V (i + 1, j − 1) + Vj Complexity? Θ(n2 ) · Θ(1) = Θ(n2 ) Example of Greedy Failing for Optimal BST prob­ lem Thanks to Nick Davis! 5 Lecture 10 6.046J Spring 2015 Introduction 10 2 8 1 3 1 9 4 Figure 1: cost = 1 × 2 + 10 × 1 + 8 × 2 + 9 × 3 = 55 8 3 9 10 2 4 1 1 Figure 2: cost = 1 × 3 + 10 × 2 + 8 × 1 + 9 × 2 = 49 6