Question

4. [15] Dynamic Programming. We are given a set of matrices Ap.A1, A2. .. .An-1. which we must multiply in this order. We let (d, dira) be the dimension of matrix A. The minimal number Nij of operations required to multiply matrices (A, Ati .. A) is defined by: a. Explain this formula. Apply this formula to compute the optimal parenthetization of the product of matrices Ao-A1,Az,A3, where the dimensions of these matrices are, respectively: 6x15, and 15x12. b. 10x8, 8x6,

10×8,8×6,6×15,15×12

Answer 1

A) this formula states that optimal number of multiplication required to for Matrix A_{i, j} = Multiplication required for matrix A_{i, k} + A _{k+1, j} and the number of multiplication required to multplity these two matrices. And we find the matrix which produces the minimum number of multiplication from all matrices

b) Number of multiplication required will be 2280

parenthetization will be as follows

((10x 8, 8 x 6 ) , (6x 15, 15 x 12))