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 pair $v_{ij}$, where $i \le j$.

  • If $i = j$, the vertex $v_{ij}$ has no output edge.
  • If $i < j$, for each $k$, s.t. $i \le k < j$, the subproblem graph contains edges $(v_{ij}, v_{ik})$ and $(v_{ij}, v_{k+1, j})$, and 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 = 1}^n = \frac{n(n + 1)}{2}.$$

The number of edges is

$$\sum_{i = 1}^n \sum_{j = 1}^n (j - i) = \frac{(n - 1)n(n + 1)}{6}.$$

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.)

We count the number of times that we reference a different entry in $m$ than the one we are computing, that is, $2$ times the number of times that line 10 runs.

$$ \begin{aligned} \sum_{l = 2}^n \sum_{i = l}^{n - l + 1} \sum_{k = i}^{i + l - 2} 2 & = \sum_{l = 2}^n \sum_{i = 1}^{n - l + 1} 2(l - 1) \\ & = \sum_{l = 2}^n 2(l - 1)(n - l + 1) \\ & = \sum_{l = 1}^{n - 1} 2l(n - l) \\ & = 2n \sum_{l = 1}^{n - 1} l - 2 \sum_{l = 1}^{n - 1} l^2 \\ & = n^2(n - 1) - 2 \cdot \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.

We proceed by induction on the number of matrices. A single matrix has no pairs of parentheses. Assume that a full parenthesization of an $n$-element expression has exactly $n − 1$ pairs of parentheses. Given a full parenthesization of an $(n + 1)$-element expression, there must exist some $k$ such that we first multiply $B = A_1 \cdots A_k$ in some way, then multiply $C = A_{k + 1} \cdots A_{n + 1}$ in some way, then multiply $B$ and $C$. By our induction hypothesis, we have $k − 1$ pairs of parentheses for the full parenthesization of $B$ and $n + 1 − k − 1$ pairs of parentheses for the full parenthesization of $C$. Adding these together, plus the pair of outer parentheses for the entire expression, yields $k - 1 + n + 1 - k - 1 + 1 = (n + 1) - 1$ parentheses, as desired.