6.006- Introduction to Algorithms Lecture 18 Prof. Constantinos Daskalakis CLRS 15Menu • New technique: Dynamic Programming Computing Fibonacci numbers – Warmup “Definition” of DP Crazy Eights PuzzleFibonacci 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 ? • Better algorithm ? O(Fn)!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 arrayDynamic Programming • DP ≈ Recursion + Memoization • DP works when: the solution can be produced by combining solutions of subproblems; the solution of each subproblem can be produced by combining solutions of sub-subproblems, etc; moreover…. the total number of subproblems arising recursively is polynomial. Fn=Fn-1+Fn-2 Fn-1=Fn-2+Fn-3 Fn-2=Fn-3+Fn-4 F1, F2,…, FnFn=Fn-1+Fn-2 F1, F2,…, Fn Dynamic Programming • DP ≈ Recursion + Memoization • DP works when: the solution can be produced by combining solutions of subproblems; the solution of each subproblem can be produced by combining solutions of sub-subproblems, etc; moreover…. the total number of subproblems arising recursively is polynomial. Optimal substructure The solution to a problem can be obtained by solutions to subproblems. Overlapping Subproblems A recursive solution contains a “small” number of distinct subproblems (repeated many times) Fn=Fn-1+Fn-2 F1, F2,…, FnCrazy 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 exampleAlgorithm • 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 • 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 RecursiveImplementations (cont.) memo = { } for i=n-1 downto 0 memo[i]= 1+maxj>i, c[i] ~ c[j] memo[j] return maximum value in memo Iterative Runtime: O(n2)Dynamic Programming • DP ≈ Recursion + Memoization • DP works when: the solution can be produced by combining solutions of subproblems; the solution of each subproblem can be produced by combining solutions of sub-subproblems, etc; moreover…. the total number of subproblems arising recursively is polynomial. Optimal substructure An solution to a problem can be obtained by solutions to subproblems. Overlapping Subproblems A recursive solution contains a “small” number of distinct subproblems (repeated many times) trick(0), trick(1),…, trick(n-1) trick(i) = 1+ maxj>i, c[i] ~ c[j] trick(j)Menu • New technique: Dynamic Programming Computing Fibonacci numbers – Warmup “Definition” of DP Crazy Eights Puzzle Next Time: all-pairs shortest pathsAll-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 cyclesDynamic Programming Approach • Consider the n × n matrix A = (aij), where aij=w(i,j) if (i,j) ∈ E, and define dij(m) = 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 }. weight of a shortest path from i to j that uses at most m edges!Proof of Claim …!≤!m‐1!edges!≤!m‐1!edges!i j k’s dij(m) = mink{dik(m–1) + akj } for k ← 1 to n if dij > dik + akj dij ← dik + akj RelaxationDynamic Programming Approach • Consider the n × n matrix A = (aij), where aij=w(i,j) if (i,j) ∈ E, and define dij(m) = 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 weight of a shortest path from i to j that uses at most m
View Full Document
Unlocking...