Dynamic Programming• Explores the space of all possible solutions– Decompose a problem into a series of subproblems– Build up correct solutions to larger and larger subproblemsBackgroundsBackgrounds• The term Dynamic Programmingcomes from Control Theory•Programmingrefers to the use of tables (arrays) to construct a solution.• Used extensively in "Operation Research" taught in the Math dept.Key Idea• Dynamic programming usually reduces timeby using more space• Solve the problem by solving subproblems of increasing size, while saving each optimal solution for a subproblem in a table• Use the table to find the optimal solution to larger problems. • Time is saved since each subproblem is solved only onceWhen is Dynamic Programming used?•Used for problems in which an optimal solution for the original problem can be found from optimal solutions to subproblems of the original problem•A recursive algorithm based on the divide and conquer approach can solve the problem. But the recursive algorithm may compute the optimal solution to the same subproblemmore than once and, therefore, it is slow. – Fibonacci term and binomial coefficient have such inefficient recursive algorithms– fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)– More details on fibonacci term and binomial coefficient later•To reduce time, compute the optimal solution of a subproblem only once and save its value. Reuse the saved value whenever the same subproblem needs to be solved.Steps to Design a Dynamic Programming Algorithm• Establish a recursive property giving the solution to an instance of the problem• Solve an instance of the problem in a bottom-up fashion by solving smaller instances first– Recall that divide & conquer is top-down– Divide and conquer blindly divides a problem into smaller instances• A divide & conquer algorithm, e.g., the recursive nthFibonacci term alg. (Algorithm 1.6), may solve the same instance more than once  SlowPrinciple of Optimality(Optimal Substructure)• Principle of optimality–Given an optimal sequence of decisions or choices, each subsequence must also be optimal.• The principle of optimality applies to a problem (not an algorithm)–A large number of optimization problems satisfy this principle. Examples follow.Principle of optimality -Shortest path problemProblem: Given a graph Gand vertices sand t, find a shortest path in Gfrom sto tTheorem: A subpath P’(from s’to t’) of a shortest path P is a shortest path from s’to t’of the subgraph G’induced by P’. Subpathsare paths that start or end at an intermediate vertex of P.Proof: If P’ was not a shortest path from s’ to t’ in G’, we can substitute the subpath from s’ to t’ in P by the shortest path in G’ from s’ to t’. The result is a shorter path from s to t than P. This contradicts our assumption that P is a shortest path from s to t.Principle of optimality: ab c dfeG’G3 1356P’={(c.d), (d,e)}P={ (a,b), (b,c) (c,d), (d,e)}P’ must be a shortest path from c to e in G’. Otherwise, P cannot be a shortest path from a to e in G.10713Principle of optimality MST (minimum spanning tree) problem• Spanning tree: A tree connecting all the vertices in an undirected connected graph• Minimum spanning tree: A spanning tree with the minimum weightPrinciple of optimality - MST problem•Problem: Given an undirected connected graph G, find a minimum spanning tree•Theorem: Any subtreeT’of an MST Tof Gis an MSTof the subgraphG’of Ginduced by the vertices of the subtree. Proof: If T’is not an MSTof G’, we can substitute the edges of T’in T, with the edges of an MST of G’. This would result in a lower cost spanning tree, contradicting our assumption that Tis an MSTof G.Principle of optimalityab c dfeG’G3 1356T’={(c.d), (d,f), (d,e)}T={(c.d), (d,f), (d,e), (a,b), (b,c)}T’ must be an MST of G’, otherwise T cannot be an MST102A problem that does not satisfy the Principle of OptimalityProblem: What is the longest simple route between City A and B? –Simple route  Never visit the same spot twice.•The longest simple route (solid line) has city C as an intermediate city.•It does not consist of the longest simple route from A to C plus the longest simple route from C to B.ACDBLongest A to BLongest C to BLongest A to CFibonacci's SeriesFibonacci's Series:• Definition: S0= 0,S1= 1,Sn= Sn-1+ Sn-2n>10, 1, 1, 2, 3, 5, 8, 13, 21, …• Applying the recursive definition we get:fib(n)1. ifn< 22. returnn3. else return (fib(n-1) + fib(n -2))Analysis using Substitution of Recursive Fibonacci• Let T(n) be the number of additions done by fib(n)• T(n)=T(n-1)+T(n-2)+1 for n>=2T(2)=1 T(1)=T(0)=0• T(n) ∈O(2n), T(n) ∈Ω(2n/2)What does the Execution Tree look like?Fib(5)+Fib(4)+Fib(3)+Fib(3)+Fib(2)+Fib(2)+Fib(1)Fib(2)+Fib(1)Fib(1) Fib(0)Fib(1) Fib(0) Fib(1) Fib(0)Dynamic Programming Solution for Fibonacci•Build a table with the first nFibonacci numbers.fib(n)1. A[0] =02. A[1] = 13. for i ←←←←2 to n4. do A[ i] = A [i -1] + A[i-2 ]5. return AIs there a recurrence equation?What is the run time?What is the space requirements?If we only need the nth number can we save space?Binomial CoefficientThe Binomial Coefficient==−+−−=<<−= or 0 1n<k<0 1110for )!(!!nkkknknknnkknknknThe recursive algorithmbinomialCoef(n, k)1. ifk= 0 or k= n2. then return 13. else {return (binomialCoef( n-1, k-1) + binomialCoef(n-1, k))}binomialCoef(n, k)1. ifk= 0 or k= n2. then return 13. else return (binomialCoef( n-1, k-1) + binomialCoef(n-1, k))nk( )n -1k -1) n-1k( )(n -2k -2n -2k -1n -2k -1n -2k ((( (n -3k -3n -3k -2n -3k -2n -3k -1n -3k -2n -3k -1n -3k -1n -3k ((((( ( (() ))))))))) ))The Call TreeDynamic Programming Solution• Use a matrix B of n+1 rows, k+1 columns where •Establisha recursive property. Rewrite in terms of matrix B:B[ i , j]= B[i -1, j-1] + B[i-1, j], 0 < j< i1 , j= 0 or j = i• Solve all “smaller instances of the problem” in a bottom-upfashion by computing the rows in Bin sequence starting with the first row.=knknB ],[The B Matrix0 1 2 3 4 ... j k01234in11 11 2 11 3 3 11 4 6 4 1B[i -1, j -1] B[i -1, j ]B[ i, j ]Compute B[4,2]= •Row 0: B[0,0] =1•Row 1: B[1,0] = 1B[1,1] = 1•Row 2: B[2,0] = 1B[2,1] = B[1,0] + B[1,1] = 2 B[2,2] = 1•Row 3: