6.006-Introduction toAlgorithms6.006Introduction to AlgorithmsLecture 18Dynamic Programming IProfManolis KellisProf.Manolis KellisCLRS 15.3, 15.4Course VI - 6.006 – Module VI – This is itDynamic Programming2Dynamic Programming•Optimization technique widely applicable•Optimization technique, widely applicableOptimal substructure Overlapping subproblemsToday: Simple examples alignment•Today: Simple examples, alignment– Simple examples: Fibonacci, Crazy EightsAli t Edit di t l l l ti–Alignment: Edit distance, molecular evolution• Thursday: More DPAli t B d Li S Affi G–Alignment: Bound, Linear Space, Affine Gaps– 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• Fibonacci numbers– Top-down vs. bottom-up• Principles of Dynamic programmingpypgg– Optimal sub-structure, repeated subproblems•Crazy EightsCrazy Eights– One-dimensional optimization•Sequence alignment•Sequence alignment– Two-dimensional optimization1 Fibonacci Computation1. Fibonacci Computation(not really an optimization problem, but similar intuition applies))A simple introduction to Dynamic Programming• Fibonacci numbers5558133253421Fibonacci numbers are ubiquitous in natureRabbits per generationLeaves per heightRabbits per generationLeaves per heightRomanesque spirals Nautilus size Coneflower spirals Leaf orderingComputing 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]Lessons from iterative Fibonacci algorithm• What did the iterative solution do?– Reveal identical sub-problems1F[1]fib_table–Order computation to enable result reuse– Systematically filled-in table of resultsExpressed larger problems from their subparts3F[4]2F[3]1F[2]–Expressed larger problems from their subparts• Ordering of computations matters–Naïve top-down approach very slow13F[7]8F[6]5F[5]ppp y• results of smaller problems not available• repeated workSf55F[10]34F[9]21F[8]–Systematic bottom-up approach successful• Systematically solve each sub-problem•Fill-in table of sub-problem results in order?F[12]89F[11]Fillin table of subproblem results in order. • Look up solutions instead of recomputingDynamic Programming in TheoryHll k fD i P i•Hallmarks of Dynamic Programming– Optimal substructure: Optimal solution to problem (instance) contains optimal solutions to sub-problems() pp– Overlapping subproblems: Limited number of distinct subproblems, repeated many many timesTypically for optimization problems ()•Typically for optimization problems (unlike Fib example)– Optimal choice made locally: max( subsolution score)–Score is typically added through the search spaceScore is typically added through the search space– Traceback common, find optimal path from indiv. choices• Middle of the road in range of difficulty– Easier: greedy choice possible at each step– DynProg: requires a traceback to find that optimal pathHarder: no opt substr e g subproblem dependencies–Harder: no opt. substr., e.g. subproblem dependenciesHallmarks 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 choicesgyDynamic Programming in Practice•Setting up dynamic programming•Setting up dynamic programming1. Find ‘matrix’ parameterization (# dimensions, variables)2. Make sure sub-problem space is finite! (not exponential)pp (p)• If not all subproblems are used, better off using memoization• If reuse not extensive, perhaps DynProg is not right solution!3Traversal order: sub-results ready when you need them3.Traversal order: subresults ready when you need them• Computation order matters! (bottom-up, but not always obvious)4Recursion formula: larger problems = F(subparts)4.Recursion formula: larger problems = F(subparts)5. Remember choices: typically F() includes min() or max()• Need representation for storing pointers, is this polynomial !• Then start computing1. Systematically fill in table of results, find optimal score2Traceback from optimal score findoptimal solution2.Trace-back from optimal score, findoptimal solution2 Crazy Eights2. Crazy EightsOne-dimensional OptimizationCrazy 8sCrazy 8s• Input: a sequence of cards c[0]…c[n-1]. 8 E.g., 7♣ 7♥ K♣ K♠8♥ … • Goal: find the longest “trick subsequence” c[i1]c[ik]wherei1<i2<<ikc[i1]…c[ik], where i1<i2<…<ik.• For it to be a trick subsequence, it must be that: j, c[ij]and c[ij+1]“match” i.e. j,[j][j+1]• they either have the same rank, • or the same suit fh i 8• or one of them is an 8 • in this case, we write: c[ij] ~ c[ij+1]Eg 7♣K♣K♠8♥is the longest such subsequenceE.g., 7♣K♣K♠8♥is the longest such subsequence in the above exampleCrazy8: Example computationCrazy8: Example computationi=1i=2i=3i=4i=5i=1i=2i=3i=4i=5c[i]7♣ 7♥ K♣ K♠ 8♥max score[i]1 2234[]Rules: •same ranksame rank• or same suit • or one is an 8Dynamic 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:
View Full Document
Unlocking...