6 006 Introduction to Algorithms 6 006 Lecture 19 Dynamic Programming II Prof Manolis Kellis Prof CLRS 15 4 25 1 25 2 Course VI 6 006 Module VI This is it Dynamic Programming 2 Dynamic Programming Optimization technique technique widely applicable Optimal substructure Overlapping subproblems Tuesday Simple examples examples alignment Fibonacci top down vs bottom up Crazy C Ei Eights ht one dimensional di i l optimization ti i ti Today More DP Alignment Ali t Edit distance di t molecular l l evolution l ti 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 II Optimal O i l sub structure b repeated d subproblems b bl Review Simple DP problems Fibonacci numbers Top down vs bottom up Crazy Eights One dimensional optimization LCS Edit Distance Sequence alignment Two Two dimensional dimensional optimization Matrix path duality Setting up the recurrence Fill Matrix Traceback All pairs shortest paths na ve 2n n n BelFo BelFo n4 Representing solutions Two ways to set up DP Matrix multiplication n3lgn lgn Floyd Floyd Warshall Warshall n3 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 1 Fibonacci Computation 1 not really an optimization problem but similar intuition applies 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 2 Crazy Eights 2 One dimensional Optimization Crazy8 Example computation i 1 i 2 i 3 i 4 i 5 c i 7 7 K K 8 max score i i 1 2 2 3 4 Input a sequence of cards c 0 c n 1 Goal find the longest trick subsequence c i1 c i c ik where i1 i2 ik Rules same rank or same suit or one is an 8 DP solution Bottom up up solving of all tricks ending in i Bottom Re use computation by saving solutions Remember optimal choice and trace back 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 optimal Contradiction original trick was supposedly optimal Overlapping sub problems To compute trick ending at i 5 need i 4 and i 3 and i 2 and i 1 To T compute t trick t i k ending di att i 4 i 4 need d i 3 i 3 i 2 i 2 i 1 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 onlyy a small number of distinct subproblems p exists c i max score i i 1 7 1 i 2 7 2 i 3 K 2 i 4 K 3 i 5 8 4 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 Today Dynamic programming II Optimal O i l sub structure b repeated d subproblems b bl Review Simple DP problems Fibonacci numbers Top down vs bottom up Crazy Eights One dimensional optimization LCS Edit Distance Sequence alignment Two Two dimensional dimensional optimization Matrix path duality Setting up the recurrence Fill Matrix Traceback All pairs shortest paths na ve 2n n n BelFo BelFo n4 Representing solutions Two ways to set up DP Matrix multiplication n3lgn lgn Floyd Floyd Warshall Warshall n3 3 Sequence Alignment aka Edit Distance aka Distance aka aka LCS LCS Longest common subsequence T Two dimensional di i l optimization ti i ti Calculate sequence alignment score recursively i S A C G T C A T C A T T A G T G T C A j Na ve enumeration method exponential alignments Given additive scoring function Constant cost of mutation reward of match e g 1 1 Unit cost of insertion deletion e g g 2 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 E Entry M M m n holds h ld optimal i l score ffor ffullll S S T T alignment li Trace back choices to obtain the actual alignment Storing the score of aligning S 1 i to T 1 j in M i j S 1 i S 1 i i T 1 j j i j Entries that may be needed for M i j Entries that M i j may be needed for The rest Reusing computation recursion formula i S1 S2 A C G T C A T C A T A G T T G T C A M i j j Score of best alignment of S1 1 i and S2 1 j is max of Score of S 1 i 1 T 1 j cost of gap in S S1 A C G S2 T A G T T G T T gap M i j M i 1 j gap Score of S …
View Full Document
Unlocking...