Chapter 8.1, Problem 57E

Dynamic programming can be used to develop an algorithm for solving the matrix-chain multiplication problem introduced in Section 3.3. This is the problem of determining how the product $A_1,A_2,\mathrm{...},A_n$ , can be computed using the fewest integer multiplications, where $A_1,A_2,\mathrm{...},A_n$ , are $m_1\times m_2,m_2\times m_3,\mathrm{...},m_n\times m_{n+1}$ matrices, respectively, and each matrix has integer entries. Recall that by the associative law, the product does not depend on the order in which the matrices are multiplied.

a) Show that the brute-force method of determining the minimum number of integer multiplications needed to solve amatrix-chain multiplication problem has exponential worst-case complexity. [Hint: Do this by first showing that the order of multiplication of matrices is specified by parenthesizing the product. Then, use Example 5 and the result of part (c) of Exercise 43 in Section 8.4.)

b) Denote by $A_{ij}$ the product $A_i{A}_{i+1},\mathrm{...},A_j$ and M (i, f) the minimum number of integer multiplications required to find $A_{ij}$ . Show that if the least number of integer multiplications are used to compute $A_{ij}$ , where $i<j$ , by splitting the product into the product of $A_i$ through $A_k$ and the product of $A_{k+1}$ through $A_j$ then the first k terms must be parenthesized so that $A_{jk}$ is computed in the optimal way using M (i, k) integer multiplications, and $A_{k+1}$ must be parenthesized so that $A_{k+1},j$ is computed in the optimal way using $M\left(k+1,j\right)$ integer multiplications.

c) Explain why part (b)leads to the recurrence relation $M\left(i,j\right)={\min }_{i\le j<k}\left(M\left(i,k\right)+M\left(k+1,j\right)+m_i{m}_{k+1},m_{j+1}\right)$ if $1\le i\le j<j\le n$ .d) Use the recurrence relation in part (c) to construct an efficient algorithm for determining the order the n matrices should be multiplied to use the minimum number of integer multiplications. Store the partial results M (i, j) as you find them so that your algorithm will not have exponential complexity.

e) Show that your algorithm from part (d) has 0(n³) worst-case complexity in terms of multiplications of integers.