15.2 Matrix-chain multiplication

15.2-1

Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is $\langle 5, 10, 3, 12, 5, 50, 6 \rangle$.

$$((5 \times 10)(10 \times 3))(((3 \times 12)(12 \times 5))((5 \times 50)(50 \times 6))).$$

15.2-2

Give a recursive algorithm $\text{MATRIX-CHAIN-MULTIPLY}(A, s, i, j)$ that actually performs the optimal matrix-chain multiplication, given the sequence of matrices $\langle A_1, A_2, \ldots ,A_n \rangle$, the $s$ table computed by $\text{MATRIX-CHAIN-ORDER}$, and the indices $i$ and $j$. (The initial call would be $\text{MATRIX-CHAIN-MULTIPLY}(A, s, 1, n)$.)

 1 2 3 4 5 6 7 8 MATRIX-CHAIN-MULTIPLY(A, s, i, j) if i == j return A[i] if i + 1 == j return A[i] * A[j] b = MATRIX-CHAIN-MULTIPLY(A, s, i, s[i, j]) c = MATRIX-CHAIN-MULTIPLY(A, s, s[i, j] + 1, j) return b * c 

15.2-3

Use the substitution method to show that the solution to the recurrence $\text{(15.6)}$ is $\Omega(2^n)$.

Suppose $P(n) \ge c2^n$,

\begin{aligned} P(n) & \ge \sum_{k = 1}^{n - 1} c2^k \cdot c2^{n - k} \\ & = \sum_{k = 1}^{n - 1} c^2 2^n \\ & = c^2 (n - 1) 2^n \\ & \ge c^2 2^n & (n > 1) \\ & \ge c 2^n. & (c \ge 1) \end{aligned}

15.2-4

Describe the subproblem graph for matrix-chain multiplication with an input chain of length $n$. How many vertices does it have? How many edges does it have, and which edges are they?

The vertices of the subproblem graph are the ordered pairs $v_{ij}$, where $i \le j$. If $i = j$, then there are no edges out of $v_{ij}$. If $i < j$, then for every $k$ such that $i \le k < j$, the subproblem graph contains edges $(v_{ij}, v_{jk})$ and $(v_{ij}, v_{k + 1, j})$. These edges indicate that to solve the subproblem of optimally parenthesizing the product $A_i \cdots A_j$, we need to solve subproblems of optimally parenthesizing the products $A_i \cdots A_k$ and $A_{k + 1} \cdots A_j$. The number of vertices is

$$\sum_{i = 1}^n\sum_{j = i}^n 1 = \frac{n(n + 1)}{2},$$

and the number of edges is

\begin{aligned} \sum_{i = 1}^n\sum_{j = i}^n (j - i) & = \sum_{i = 1}^n\sum_{t = 0}^{n - i} t & \text{(substituting t = j - i)} \\ & = \sum_{i = 1}^n \frac{(n - i)(n - i + 1)}{2}. \end{aligned}

Substituting $r = n - i$ and reversing the order of summation, we obtain

\begin{aligned} \sum_{i = 1}^n \frac{(n - i)(n - i + 1)}{2} & = \frac{1}{2} \sum_{r = 0}^{n - 1} (r^2 + r) \\ & = \frac{1}{2} \bigg(\frac{(n - 1)n(2n - 1)}{6} + \frac{(n - 1)n}{2}\bigg) & \text{(by equations (A.3) and (A.1))} \\ & = \frac{(n - 1)n(n + 1)}{6}. \end{aligned}

Thus, the subproblem graph has $\Theta(n^2)$ vertices and $\Theta(n^3)$ edges.

15.2-5

Let $R(i, j)$ be the number of times that table entry $m[i, j]$ is referenced while computing other table entries in a call of $\text{MATRIX-CHAIN-ORDER}$. Show that the total number of references for the entire table is

$$\sum_{i = 1}^n \sum_{j = i}^n R(i, j) = \frac{n^3 - n}{3}.$$

($\textit{Hint:}$ You may find equation $\text{(A.3)}$ useful.)

Each time the $l$-loop executes, the $i$-loop executes $n - l + 1$ times. Each time the $i$-loop executes, the $k$-loop executes $j - i = l - 1$ times, each time referencing $m$ twice. Thus the total number of times that an entry of $m$ is referenced while computing other entries is $\sum_{l = 2}^n (n - l + 1)(l - 1)2$. Thus,

\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^n R(i, j) & = \sum_{l = 2}^n (n - l + 1)(l - 1)2 \\ & = 2 \sum_{l = 1}^{n - 1} (n - l)l \\ & = 2 \sum_{l = 1}^{n - 1} nl - 2 \sum_{l = 1}^{n - 1} l^2 \\ & = 2 \frac{n(n - 1)n}{2} - 2\frac{(n - 1)n(2n - 1)}{6} \\ & = n^3 - n^2 - \frac{2n^3 - 3n^2 + n}{3} \\ & = \frac{n^3 - n}{3}. \end{aligned}

15.2-6

Show that a full parenthesization of an $n$-element expression has exactly $n - 1$ pairs of parentheses.

$n - 1$ multiplications.