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

C++
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 = i}^n = \frac{n(n + 1)}{2}.\]

The number of edges is

\[\sum_{i = 1}^n \sum_{j = i}^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 = 1}^{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.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用