6.006-Introduction to Algorithms6.006Introduction to AlgorithmsLecture 19Dynamic Programming IIProf Manolis KellisProf. Manolis KellisCLRS 15.4, 25.1, 25.2Course VI - 6.006 – Module VI – This is itDynamic Programming2Dynamic Programming•Optimization technique widely applicable•Optimization technique, widely applicableOptimal substructure Overlapping subproblemsTuesday: Simple examples alignment•Tuesday: Simple examples, alignment– Fibonacci: top-down vs. bottom-upCEihtdi i l ti i ti–Crazy Eights: one-dimensional optimization• Today: More DPAli t Edit di t l l l ti–Alignment: Edit distance, molecular evolution– Back to paths: All Pairs Shortest Paths DP1,DP2Nt k•Next week: – Knapsack (shopping cart) problemf–Text Justification– Structured DP: Vertex Cover on trees, phylogenyToday: Dynamic programming IIOi l bdbbl•Optimal sub-structure, repeated subproblems• Review: Simple DP problems– Fibonacci numbers: Top-down vs. bottom-up– Crazy Eights: One-dimensional optimization• LCS, Edit Distance, Sequence alignment–Two-dimensional optimization: Matrix/path dualityTwodimensional optimization: Matrix/path duality– Setting up the recurrence, Fill Matrix, Traceback•All pairs shortest paths (naïve: 2nn*BelFo:n4)•All pairs shortest paths (naïve: 2n. nBelFo: n4)– Representing solutions. Two ways to set up DPMatrix multiplication: n3lgn FloydWarshall:n3–Matrix multiplication: n3lgn. Floyd-Warshall: n3Hallmarks of optimization problemsGreedy algorithmsDynamic Programming1. Optimal substructureAn optimal solution to a problem (instance)Greedy algorithmsDynamic ProgrammingAn optimal solution to a problem (instance) contains optimal solutions to subproblems.2. Overlapping subproblemsA recursive solution contains a “small” number fditi t b bl t d tiof distinct subproblems repeated many times.3G d hi3. Greedy choice propertyLocally optimal choices lead to globally optimal solutionGreedy Choice is not possibleGlobally optimal solution requires trace back through many choicesgy1 Fibonacci Computation1. Fibonacci Computation(not really an optimization problem, but similar intuition applies))Computing Fibonacci numbers: Top down• Fibonacci numbers are defined recursively: y– Python codedef fibonacci(n): if n==1 or n==2: return 1return fibonacci(n-1) + fibonacci(n-2)• Goal: Compute nthFibonacci number. –F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2)F(0) 1, F(1) 1, F(n) F(n1) F(n2)– 1,1,2,3,5,8,13,21,34,55,89,144,233,377,…• Analysis: – T(n) = T(n-1) + T(n-2) = (…) = O(2n)Computing Fibonacci numbers: Bottom up•Top-down approach•Top-down approach– Python codedef fibonacci(n): fib table()fib_table[1] = 1fib_table[2] = 1for i in range(3,n+1): fib table[i] = fib table[i-1]+fib table[i-2]2F[3]1F[2]1F[1]fib_table– Analysis: T(n) = O(n)_[] _[]_ []return fib_table[n]8F[6]5F[5]3F[4]2F[3]34F[9]21F[8]13F[7]8F[6]89F[11]55F[10]34F[9]?F[12]2 Crazy Eights2. Crazy EightsOne-dimensional OptimizationCrazy8: Example computationi=1 i=2 i=3 i=4 i=5c[i]7♣7♥K♣K♠8♥c[i]7♣7♥K♣K♠8♥max [i]1 2234score[i]Input: a sequence of cards c[0]…c[n-1]. Goal: find the longest “trick subsequence” c[i1]c[ik]wherei1<i2<<ikRules: • same rankc[i1]…c[ik], where i1<i2<…<ik.DP solution: •Bottom-up solving of all tricks ending ini• or same suit • or one is an 8 Bottomup solving of all tricks ending in i• Re-use computation by saving solutions• Remember optimal choice and trace backWhy DP applies to Crazy Eights?Why DP applies to Crazy Eights?Optimal substructure: • Optimal trick that uses card i must contain optimal trick that ends in card i. • Proof (cut-and-paste argument): If not the case, replace sub-optimal trick ending in i with better trick ending in i, leading to better score overall•Contradiction: original trick was supposedly‘optimal’Contradiction: original trick was supposedly optimalOverlapping sub-problems: • To compute trick ending at i=5, need i=4 and i=3 and i=2 and i=1Tttikditi4di3i2i1•To compute trick ending at i=4, need i=3, i=2, i=1• etc… naïve T(n)=T(n-1)+T(n-2)+T(n-3)… naïve T(n) is exponential in n• However, only a small number of distinct subproblems exists,ypi=1 i=2 i=3 i=4 i=5c[i]7♣7♥K♣K♠8♥c[i]7♣7♥K♣K♠8♥max score[i]12234Dynamic Programming for Crazy Eights•Setting up dynamic programming•Setting up dynamic programming1. Find ‘matrix’ parameterization One-dimensional arrayy2. Make sure sub-problem space is finite! (not exponential) Indeed, just one-dimensional array3Tldblt d h d th3.Traversal order: sub-results ready when you need them Left-to-right ensures this4.Recursion formula: larger problems=F(subparts)4.Recursion formula: larger problems F(subparts) Scan entire sub-array completed so far O(n) each step5. Remember choices: typically F() includes min() or max() Pointer back to the entry that gave us optimal choice• Then start computing1Systematically fill in table of results find optimal score1.Systematically fill in table of results, find optimal score2. Trace-back from optimal score, find optimal solutionToday: Dynamic programming IIOi l bdbbl•Optimal sub-structure, repeated subproblems• Review: Simple DP problems– Fibonacci numbers: Top-down vs. bottom-up– Crazy Eights: One-dimensional optimization• LCS, Edit Distance, Sequence alignment–Two-dimensional optimization: Matrix/path dualityTwodimensional optimization: Matrix/path duality– Setting up the recurrence, Fill Matrix, Traceback•All pairs shortest paths (naïve: 2nn*BelFo:n4)•All pairs shortest paths (naïve: 2n. nBelFo: n4)– Representing solutions. Two ways to set up DPMatrix multiplication: n3lgn FloydWarshall:n3–Matrix multiplication: n3lgn. Floyd-Warshall: n33. Sequence Alignment(aka Edit Distance aka LCS(aka. Edit Distance, aka. LCS, Longest common subsequence)Tdi i l ti i tiTwo-dimensional optimizationCalculate sequence alignment score recursivelySiAC G T CAT CAT A G T G T C AST• Naïve enumeration method: exponential # alignments•Given additive scoring function:jGiven additive scoring function:– Constant cost of mutation / reward of match (e.g. 1,-1)–Unit cost of insertion / deletion (e.g. -2)(g)• Dynamic programming approach: – Compute all prefix-to-prefix alignments bottom-up– Matrix M[i,j] holds best alignment score S[1..i], T[1..j]– Express Score(i,j)=F( previously-computed scores )EM[]hld il ffllSTli–Entry M[m,n] holds
View Full Document
Unlocking...