This chapter provides knowledge of dynamic programming. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Dynamic Programming 3/29/14 21:19 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Dynamic Programming © 2014 Goodrich, Tamassia, Goldwasser Dynamic Programming 1 Matrix Chain-Products ! Dynamic Programming is a general algorithm design paradigm. n n Rather than give the general structure, let us first give a motivating example: Matrix Chain-Products ! Review: Matrix Multiplication. n n C = A*B A is d × e and B is e × f e −1 n O(def ) time © 2014 Goodrich, Tamassia, Goldwasser d B j e e C[i, j ] = ∑ A[i, k ] * B[k , j ] k =0 f A i Dynamic Programming C i,j f d 2 1 Dynamic Programming 3/29/14 21:19 Matrix Chain-Products ! Matrix Chain-Product: n n n Compute A=A0*A1* *An-1 Ai is di × di+1 Problem: How to parenthesize? ! Example n n n n n B is 3 × 100 C is 100 × 5 D is 5 × 5 (B*C)*D takes 1500 + 75 = 1575 ops B*(C*D) takes 1500 + 2500 = 4000 ops © 2014 Goodrich, Tamassia, Goldwasser Dynamic Programming 3 An Enumeration Approach ! Matrix Chain-Product Alg.: n n n Try all possible ways to parenthesize A=A0*A1* *An-1 Calculate number of ops for each one Pick the one that is best ! Running time: n n n n The number of paranethesizations is equal to the number of binary trees with n nodes This is exponential! It is called the Catalan number, and it is almost 4n. This is a terrible algorithm! © 2014 Goodrich, Tamassia, Goldwasser Dynamic Programming 4 2 Dynamic Programming 3/29/14 21:19 A Greedy Approach ! Idea #1: repeatedly select the product that uses (up) the most operations. ! Counter-example: n n n n n n A is 10 × 5 B is 5 × 10 C is 10 × 5 D is 5 × 10 Greedy idea #1 gives (A*B)*(C*D), which takes 500+1000+500 = 2000 ops A*((B*C)*D) takes 500+250+250 = 1000 ops © 2014 Goodrich, Tamassia, Goldwasser Dynamic Programming 5 Another Greedy Approach ! Idea #2: .
