6.006 Lecture 21: String Subproblems, Psuedopolynomial Time; Parenthesization, Edit Distance, Knapsack

Lecture 21 Dynamic Programming III of IV 6.006 Fall 2011 Lecture 21: Dynamic Programming III Lecture Overview • Subproblems for strings • Parenthesization • Edit distance (& longest common subseq.) • Knapsack • Pseudopolynomial Time Review: * 5 easy steps to dynamic programming (a) define subproblems count # subproblems (b) guess (part of solution) count # choices (c) relate subproblem solutions compute time/subproblem (d) recurse + memoize problems OR build DP table bottom-up check subproblems acyclic/topological order (e) solve original problem: = a subproblem OR by combining subproblem solutions time = time/subproblem · # sub- =⇒ extra time * problems from L20 (text justification, Blackjack) are on sequences (words, cards) * useful problems for strings/sequences ) x: suffixes x[i :] Θ(|x|) prefixes x[: i] o substrings x[i : j] Θ(x2 ) ← cheaper =⇒ use if possible 1 Lecture 21 Dynamic Programming III of IV 6.006 Fall 2011 Parenthesization: Optimal evaluation of associative expression A[0] · A[1] · · · A[n − 1] — e.g., multiplying rectangular matrices A C B . C vs A (B.C) (A.B) . . . θ(n2) time θ(n) time Figure 1: 2. guessing = outermost multiplication (|{z} · · · )(|{z} ··· ) ↑k−1 ↑k =⇒ # choices = O(n) 1. subproblems = prefixes & suffixes? NO = cost of substring A[i : j] =⇒ # subproblems = Θ(n2 ) 3. recurrence: • DP[i, j] = min(DP [i, k] + DP[k, j]+ cost of multiplying (A[i] · · · A[k − 1]) by (A[k] · · · A[j − 1]) for k in range(i + 1, j)) i DAG i j k j • DP[i, i + 1] = 0 =⇒ cost per subproblem = O(j − i) = O(n) 4. topological order: increasing substring size. Total time = O(n3 ) 5. original problem = DP [0, n] (& use parent pointers to recover parens.) NOTE: Above DP is not shortest paths in the subproblem DAG! Two dependencies =⇒ not path! 2 Lecture 21 Dynamic Programming III of IV 6.006 Fall 2011 Edit Distance Used for DNA comparison, diff, CVS/SVN/. . . , spellchecking (typos), plagiarism detection, etc. Given two strings x & y, what is the cheapest possible sequence of character edits (insert c, delete c, replace c → c’) to transform x into y? • cost of edit depends only on characters c, c0 • for example in DNA, C → G common mutation =⇒ low cost • cost of sequence = sum of costs of edits • If insert & delete cost 1, replace costs 0, minimum edit distance equivalent to finding longest common subsequence. Note that a subsequence is sequential but not necessarily contiguous. • for example H I E R O G L Y P H O L O G Y vs. M I C H A E L A N G E L O =⇒ HELLO Subproblems for multiple strings/sequences • combine suffix/prefix/substring subproblems • multiply state spaces • still polynomial for O(1) strings Edit Distance DP (1) subproblems: c(i, j) = edit-distance(x[i :], y[j :]) for 0 ≤ i < |x|, 0 ≤ j < |y| =⇒ Θ(|x| · |y|) subproblems (2) guess whether, to turn x into y, (3 choices): • x[i] deleted • y[j] inserted • x[i] replaced by y[j] (3) recurrence: c(i, j) = maximum of: • cost(delete x[i]) + c(i + 1, j) if i < |x|, • cost(insert y[j]) + c(i, j + 1) if j < |y|, • cost(replace x[i] → y[j]) + c(i + 1, j + 1) if i < |x|&j < |y| base case: c(|x|, |y|) = 0 =⇒ Θ(1) time per subproblem 3 Lecture 21 Dynamic Programming III of IV 6.006 Fall 2011 (4) topological order: DAG in 2D table: 0 j |y| 0 i |x| • bottom-up OR right to left • only need to keep last 2 rows/columns =⇒ linear space • total time = Θ(|x| · |y|) (5) original problem: c(0, 0) Knapsack: Knapsack of size S you want to pack • item i has integer size si & real value vi • goal: choose subset of items of maximum total value subject to total size ≤ S First Attempt: 1. subproblem = value for suffix i: WRONG 2. guessing = whether to include item i =⇒ # choices = 2 3. recurrence:  • DP [i] = max(DP [i + 1], vi + DP [i + 1] if  si  ≤ S?!) • not enough information to know whether item i fits — how much space is left? GUESS! Correct: 1. subproblem = value for suffix i: given knapsack of size X =⇒ # subproblems = O(nS) ! 4 Lecture 21 Dynamic Programming III of IV 6.006 Fall 2011 3. recurrence: • DP [i, X] = max(DP [i + 1, X], vi + DP [i + 1, X − si ] if si ≤ X) • DP [n, X] = 0 =⇒ time per subproblem = O(1) 4. topological order: for i in n, . . . , 0: for X in 0, . . . S total time = O(nS) 5. original problem = DP [0, S] (& use parent pointers to recover subset) AMAZING: effectively trying all possible subsets! . . . but is this actually fast? Polynomial time Polynomial time = polynomial in input size • here Θ(n) if number S fits in a word • O(n lg S) in general • S is exponential in lg S (not polynomial) Pseudopolynomial Time Pseudopolynomial time = polynomial in the problem size AND the numbers (here: S, si ’s, vi ’s) in input. Θ(nS) is pseudopolynomial. Remember: polynomial — GOOD exponential — BAD pseudopoly — SO SO 5