2. (10 pts) Many scientific and engineering applications involve performing long sequences of matrix multiplications, and often the matrices are not square. Matrices M1 and M2 can be multiplied if the dimensions of Mi are a x b and the dimensions of M2 are b x c, (so Mi has the same number of columns as M2 has rows) and the product will have dimensions a x c. In this problem we will consider only the standard way to multiply two matrices, so multiplying an a x b matrix with a b x e matrix takes time abc. A sequence of matrix multiplications M1M2... Mn is defined if each Mi has dimensions d,-1 x di, so each matrix has a number of columns equal to the next matrix's number of rows. The resulting product will be do X dr Matrix multiplication is associative, so the sequence of matrices can be parenthesized in any way (but the order of the matrices cannot be changed). Parenthesizing in a clever way can greatly reduce the time required to multiply the matrices. For example consider the following product with do 8. d - 4, d2 - 10, and d3 - 3: M1 M2 M3 8x4 4x10 10x3 In this case, parenthesizing as (M1 M2) M3 takes time (8.4-10)+(8-10-3) -560 while parenthesizing as M1(M2M3) takes time (4.10.3) +(8-4.3) -216, and is more than twice as fast. The savings can easily be even more dramatic. You may want to experiment with other sequences of 3 or 4 matrices with varying dimensions. Note that the times to multiply a sequence of n matrices does not depend on the values in the matrices, only on the sequence of dimensions do, dl, . 4m Furthermore, as each matrix multiplication is done, one of the dimension from the sequence of dimensions is effectively cancelled. The cost of the multiplication is the product of three dimensions: the cancelled dimension and the two adjacent remaining dimensions. For this problem you are to create a dynamic programming problem for determining the cost of the best way to parenthesize a sequence of matrix multiplications. (a) (4 pts) By considering the last multiplication done, create a recurrence for the minimum cost to multiply a sequence of matrices with dimensions do,... , dn in terms of the minimum costs needed to multiply subsequences of the matrices. (b) (1 pt) What is "smaller" about the subproblems that must be solved? (c) (4 pts) Give a bottom-up table-filling algorithm for computing the minimum cost to multiply a sequence of matrices from the dimensions do,... ,dn. Make sure that the values needed to fill in a cell are computed before being used (d) (1 pt) Briefly describe how the table's values can be used to determine which products should be computed before the last multiplication (i.e. between which Mi and Mi+1 are separated by the outermost parentheses) in a best way to parenthesize the product. (you need only describe how to determine the "last" multiplication, and need not recursively compute the entire ordering)