Dynamic Programming IIDynamic ProgrammingElements of DP AlgorithmsApplicability to Optimization ProblemsOptimized Chain OperationsMatrix MultiplicationChain Matrix MultiplicationExample: CMMNaive AlgorithmCost of Naive AlgorithmDP Solution (I)DP Solution (II)DP Solution (III)Computing m[i, j]Slide 15Slide 16Slide 17Slide 18Matrix-Chain-Order(p)AnalysisExtracting Optimum SequenceMult (A, i, j)Example: DP for CMMFinding a Recursive SolutionSteps in DP: Step 1DP Step 2DP Step 3DP Step 4Slide 29Assembly-Line SchedulingAssembly LinesFinding SubproblemRecursive Formula for SubproblemRecursive Formula (II)Slide 36ExamplePolygonsConvex PolygonsTriangulationsExample: Polygon TriangulationMinimum-Weight Convex Polygon TriangulationCorrespondence to Binary TreesBinary Tree for TriangulationLemmaAnother Example of Binary Tree for TriangulationSlide 47Slide 48Slide 49Weighted-Polygon-Triangulation(V)Dynamic Programming IIDynamic Programming IIMany of the slides are from Prof. Plaisted’s resources at University of North Carolina at Chapel HillDynamic ProgrammingSimilar to divide-and-conquer, it breaks problems down into smaller problems that are solved recursively. In contrast, DP is applicable when the sub-problems are not independent, i.e. when sub-problems share sub-sub-problems. It solves every sub-sub-problem just once and save the results in a table to avoid duplicated computation.Elements of DP AlgorithmsSub-structure: decompose problem into smaller sub-problems. Express the solution of the original problem in terms of solutions for smaller problems.Table-structure: Store the answers to the sub-problem in a table, because sub-problem solutions may be used many times.Bottom-up computation: combine solutions on smaller sub-problems to solve larger sub-problems, and eventually arrive at a solution to the complete problem.Applicability to Optimization ProblemsOptimal sub-structure (principle of optimality): for the global problem to be solved optimally, each sub-problem should be solved optimally. This is often violated due to sub-problem overlaps. Often by being “less optimal” on one problem, we may make a big savings on another sub-problem.Small number of sub-problems: Many NP-hard problems can be formulated as DP problems, but these formulations are not efficient, because the number of sub-problems is exponentially large. Ideally, the number of sub-problems should be at most a polynomial number.Optimized Chain OperationsDetermine the optimal sequence for performing a series of operations. (the general class of the problem is important in compiler design for code optimization & in databases for query optimization)For example: given a series of matrices: A1…An , we can “parenthesize” this expression however we like, since matrix multiplication is associative (but not commutative).Multiply a p x q matrix A times a q x r matrix B, the result will be a p x r matrix C. (# of columns of A must be equal to # of rows of B.)Matrix MultiplicationIn particular for 1  i  p and 1  j  r, C[i, j] = k = 1 to q A[i, k] B[k, j] Observe that there are pr total entries in C and each takes O(q) time to compute, thus the total time to multiply 2 matrices is pqr.Chain Matrix MultiplicationGiven a sequence of matrices A1 A2…An , and dimensions p0 p1…pn where Ai is of dimension pi-1 x pi , determine multiplication sequence that minimizes the number of operations.This algorithm does not perform the multiplication, it just figures out the best order in which to perform the multiplication.Example: CMMConsider 3 matrices: A1 be 5 x 4, A2 be 4 x 6, and A3 be 6 x 2. Mult[((A1 A2)A3)] = (5x4x6) + (5x6x2) = 180Mult[(A1 (A2A3 ))] = (4x6x2) + (5x4x2) = 88Even for this small example, considerable savings can be achieved by reordering the evaluation sequence.Naive AlgorithmIf we have just 1 item, then there is only one way to parenthesize. If we have n items, then there are n-1 places where you could break the list with the outermost pair of parentheses, namely just after the first item, just after the 2nd item, etc. and just after the (n-1)th item.When we split just after the kth item, we create two sub-lists to be parenthesized, one with k items and the other with n-k items. Then we consider all ways of parenthesizing these. If there are L ways to parenthesize the left sub-list, R ways to parenthesize the right sub-list, then the total possibilities is LR.Cost of Naive AlgorithmThe number of different ways of parenthesizing n items isP(n) = 1, if n = 1P(n) = k = 1 to n-1 P(k)P(n-k), if n  2This is related to Catalan numbers (which in turn is related to the number of different binary trees on n nodes). Specifically P(n) = C(n-1). C(n) = (1/(n+1)) C(2n, n)  (4n / n3/2) where C(2n, n) stands for the number of various ways to choose n items out of 2n items total.DP Solution (I)Let Ai…j be the product of matrices i through j. Ai…j is a pi-1 x pj matrix. At the highest level, we are multiplying two matrices together. That is, for any k, 1  k  n-1, A1…n = (A1…k)(Ak+1…n)The problem of determining the optimal sequence of multiplication is broken up into 2 parts: Q: How do we decide where to split the chain (what k)?A : Consider all possible values of k.Q: How do we parenthesize the subchains A1…k & Ak+1…n?A : Solve by recursively applying the same scheme.NOTE: this problem satisfies the “principle of optimality”.Next, we store the solutions to the sub-problems in a table and build the table in a bottom-up manner.DP Solution (II)For 1  i  j  n, let m[i, j] denote the minimum number of multiplications needed to compute Ai…j .Example: Minimum number of multiplies for A3…798]7,3[7654321AAAAAAAAAm  In terms of pi , the product A3…7 has dimensions ____.DP Solution (III)The optimal cost can be described be as follows:»i = j  the sequence contains only 1 matrix, so m[i, j] = 0.»i < j  This can be split by considering each k, i  k < j, as Ai…k (pi-1 x pk ) times Ak+1…j (pk x pj). This suggests the following recursive rule for computing m[i, j]: m[i, i] = 0 m[i, j] = mini  k < j (m[i, k] + m[k+1, j] + pi-1pkpj ) for i < jComputing m[i, j]For a specific k, (Ai …Ak)( Ak+1 … Aj) =m[i, j] = mini  k < j (m[i, k] + m[k+1, j] + pi-1pkpj )Computing m[i, j]For a specific k, (Ai