6 006 Introduction to Algorithms Lecture 18 Prof Constantinos Daskalakis CLRS 15 Menu New technique Dynamic Programming Computing Fibonacci numbers Warmup Definition of DP Crazy Eights Puzzle Fibonacci Numbers Fibonacci sequence F0 0 F1 1 Fn Fn 1 Fn 2 How fast does Fn grow Fn Fn 1 Fn 2 2 Fn 2 Fn 2 n How quickly can we compute Fn time measured in arithmetic operations Fn Fn 1 Fn 2 Algorithm I recursion naive fibo n if n 0 return 0 else if n 1 return 1 else return naive fibo n 1 naive fibo n 2 Time O Fn Better algorithm Fn Fn 1 Fn 2 Algorithm II memoization memo fibo i if i in memo return memo i else if i 0 return 0 else if i 1 return 1 else f fibo i 1 fibo i 2 memo i f return f return fibo n Time O n in the whole recursive execution I will only go beyond this point n times since every time I do this I fill in another slot in memo hence all other calls to fibo act as reading an entry of an array Dynamic Programming DP Recursion Memoization DP works when the solution can be produced by combining solutions of subproblems Fn Fn 1 Fn 2 the solution of each subproblem can be produced by combining solutions of sub subproblems etc Fn 1 Fn 2 Fn 3 Fn 2 Fn 3 Fn 4 moreover the total number of subproblems arising recursively is polynomial F F F 1 2 n Dynamic Programming DP Recursion Memoization DP works when the solution can be produced by combining solutions of Optimal substructure subproblems Fn Fn 1 Fn 2 The solution to a problem can be obtained by the solution of each subproblem can be produced by solutions to subproblems F F F combining solutions of sub subproblems etc n n 1 n 2 moreover the total number of subproblems arising recursively is Overlapping Subproblems Apolynomial recursive solution contains a F small F Fnumber of 1 2 n distinct subproblems repeated many times F1 F2 Fn Crazy 8s Input a sequence of cards c 0 c n 1 E g 7 7 K K 8 Goal find the longest trick subsequence c 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 they either have the same rank or the same suit or one of them is an 8 in this case we write c ij c ij 1 E g 7 K K 8 is the longest such subsequence in the above example Algorithm Let trick i be the length of the longest trick subsequence that starts at card c i Question How can I relate value of trick i with the values of trick i 1 trick n 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 n 1 return 1 else f 1 maxj i c i c j trick j memo i f return f call trick 0 return maximum value in memo Implementations cont Iterative memo for i n 1 downto 0 memo i 1 maxj i c i c j memo j return maximum value in memo Runtime O n2 Dynamic Programming DP Recursion Memoization DP works when the solution can be produced by combining solutions of Optimal substructure subproblems An solution to a problem can be obtained by to subproblems the solutionsolutions of each subproblem can be produced by trick i 1 maxj i c i combining solutions of sub subproblems etc c j trick j moreover Overlapping Subproblems the total number of subproblems arising recursively is Apolynomial recursive solution contains a small number of distinct subproblems repeated many times trick 0 trick 1 trick n 1 Menu New technique Dynamic Programming Computing Fibonacci numbers Warmup Definition of DP Crazy Eights Puzzle Next Time all pairs shortest paths All pairs shortest paths Input Digraph G V E where V n with edge weight function w E R Output n n matrix of shortest path lengths i j for all i j V Assumption No negative weight cycles Dynamic Programming Approach Consider the n n matrix A aij where aij w i j if i j E and define dij m weight of a shortest path from i to j that uses at most m edges Claim We have dij 0 0 if i j and if i j and for m 1 2 n 1 dij m mink dik m 1 akj Proof of Claim k s dij m mink dik m 1 akj dges e 1 m i m 1 edges j for k 1 to n if dij dik akj dij dik akj Relaxation Dynamic Programming Approach Consider the n n matrix A aij where aij w i j if i j E and define dij m weight of a shortest path from i to j that uses at most m edges Claim We have dij 0 0 if i j and if i j and for m 1 2 n 1 dij m mink dik m 1 akj Time O n4 similar to n runs of Bellman Ford
View Full Document
Unlocking...