6 006 Introduction to Algorithms 6 006 Lecture 18 Dynamic Programming I Prof Manolis Kellis Prof CLRS 15 3 15 4 Course VI 6 006 Module VI This is it Dynamic Programming 2 Dynamic Programming Optimization technique technique widely applicable Optimal substructure Overlapping subproblems Today Simple examples examples alignment Simple examples Fibonacci Crazy Eights Alignment Ali t Edit distance di t molecular l l evolution l ti Thursday More DP Alignment Ali t Bound B d Linear Li Space S Affine Affi G Gaps Back to paths All Pairs Shortest Paths DP1 DP2 Next N t week k Knapsack shopping cart problem Text Justification f Structured DP Vertex Cover on trees phylogeny Today Dynamic programming Fibonacci numbers Top down vs bottom up Principles p of Dynamic y p programming g g Optimal sub structure repeated subproblems Crazy Eights One dimensional optimization Sequence alignment Two dimensional optimization 1 Fibonacci Computation 1 not really an optimization problem but similar intuition applies A simple introduction to Dynamic Programming 55 Fibonacci numbers 8 13 2 3 21 5 34 Fibonacci numbers are ubiquitous in nature Rabbits per generation Romanesque spirals Nautilus size Leaves per height Coneflower spirals Leaf ordering Computing Fibonacci numbers Top down Fibonacci numbers are defined recursively y Python code def fibonacci n if n 1 or n 2 return 1 return fibonacci n 1 fibonacci n 2 Goal Compute nth Fibonacci number F 0 F 0 1 1 F 1 F 1 1 1 F n F n F n 1 F n 2 F n 1 F n 2 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 Python code fib table fib table F 1 1 F 2 1 F 3 2 F 4 3 F 5 5 F 6 8 F 7 13 F 8 21 F 9 34 F 10 55 F 11 89 F 12 def fibonacci n fib table 1 1 fib table 2 1 for i in range 3 n 1 fib table i fib table i 1 fib table i 2 return fib table n Analysis T n O n Lessons from iterative Fibonacci algorithm fib table F 1 1 F 2 1 F 3 2 F 4 3 F 5 5 F 6 8 F 7 13 F 8 21 F 9 34 F 10 55 F 11 89 F 12 What did the iterative solution do Reveal identical sub problems Order computation to enable result reuse Systematically filled in table of results Expressed larger problems from their subparts Ordering of computations matters Na ve top down p approach pp very y slow results of smaller problems not available repeated work Systematic S bottom up approach successful f Systematically solve each sub problem Fill Fill in in table of sub problem sub problem results in order order Look up solutions instead of recomputing Dynamic Programming in Theory Hallmarks H ll k off D Dynamic i P Programming i Optimal substructure Optimal solution to problem instance contains optimal p solutions to sub problems p Overlapping subproblems Limited number of distinct subproblems repeated many many times Typically for optimization problems unlike Fib example Optimal choice made locally max subsolution score Score 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 path Harder no opt opt substr substr e g e g subproblem dependencies Hallmarks of optimization problems Greedy algorithms Dynamic Programming 1 Optimal substructure An optimal solution to a problem instance contains optimal solutions to subproblems 2 Overlapping subproblems A recursive solution contains a small number off distinct di ti t subproblems b bl repeated t d many times ti 3 Greedy 3 G d choice h i property Greedy Choice is not possible Locally optimal choices lead to globally optimal solution Globally optimal solution requires trace back through g manyy choices Dynamic Programming in Practice Setting up dynamic programming 1 Find matrix parameterization dimensions variables p space p is finite not exponential p 2 Make sure sub problem If not all subproblems are used better off using memoization If reuse not extensive perhaps DynProg is not right solution 3 Traversal order sub results 3 sub results ready when you need them Computation order matters bottom up but not always obvious 4 Recursion formula larger problems F subparts 4 5 Remember choices typically F includes min or max Need representation for storing pointers is this polynomial Then start computing 1 Systematically fill in table of results find optimal score 2 Trace back 2 Trace back from optimal score score find optimal solution 2 Crazy Eights 2 One dimensional Optimization Crazy 8s Input a sequence of cards c 0 c n 1 E g 7 7 K K 8 8 Goal find the longest trick subsequence c i1 c i c ik where i1 i2 ik For it to be a trick subsequence it must be that j c i j and c i j 1 match i e they either have the same rank or the same suit or one off them h iis an 8 in this case we write c ij c ij 1 E E g g 7 K K 8 is the longest such subsequence in the above example Crazy8 Example computation i 1 i 2 i 3 i 4 i 5 c i 7 7 K K 8 max score i 1 2 2 3 4 Rules same rank or same suit or one is an 8 Dynamic Programming for Crazy Eights Setting up dynamic programming 1 Find matrix parameterization One dimensional arrayy 2 Make sure sub problem space is finite not exponential Indeed just one dimensional array 3 Traversal 3 T l order d sub results b lt ready d when h you need d th them Left to right ensures this 4 Recursion formula larger problems F subparts Scan entire sub array completed so far O n each step 5 Remember choices typically F includes min or max Pointer back to the entry that gave us optimal choice Then start computing 1 Systematically fill in table of results 1 results find optimal score 2 Trace back from optimal score find optimal solution Crazy8 Max Score Algorithm Let trick i be the length g of the longest g trick subsequence that ends at card c i Question How can I relate value of trick i with the values of trick 1 trick i 1 Recursive formula trick i 1 maxj i c i c j trick j Maximum trick length maxi trick i Implementations Recursive memo trick i if i in memo return memo i else if i 1 return 1 else f 1 maxj i c i c j trick j memo i f return f call trick n return maximum value in memo Implementations cont Iterative memo f i 1 for i 1 to t n memo i 1 maxj i c i c j memo j return maximum i value l in …
View Full Document
Unlocking...