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} \dots A_{n}$ can be computed using the fewest integer multiplications, where $A_{1}, A_{2},\dots, A_{n}\:\text{are}\: m_{1} \times m_{2}, m_{2} \times m_{3},\dots,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.
- Show that the brute-force method of determining the minimum number of integer multiplications needed to solve a matrix-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 $(A)$ of question $41$ in Section $8.4.]$
- Denote by $A_{ij}$ the product $A_{i}A_{i+1}\dots, A_{j},$ and $M(i,j)$ 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_{ik}$ is computed in the optimal way using $M(i,k)$ integer multiplications and $A_{{k+1},j}$ must be parenthesized so that $A_{{k+1},j}$ is computed in the optimal way using $M(k+1,j)$ integer multiplications.
- Explain why part $(B)$ leads to the recurrence relation $M(i,j)=\text{min}_{i\leq k < j}(M(i,k) + M(k+1,j) + m_{i}m_{k+1}m_{j+1})\:\text{if}\:1\leq i \leq j < j\leq n.$
- 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.
- Show that your algorithm from part $(D)$ has $O(n^{3})$ worst-case complexity in terms of multiplications of integers.
