15.2.md

Exercises 15.2-1

---

Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is [5, 10, 3, 12, 5, 50, 6].

Answer

It's very easy.see my implementation

Exercises 15.2-2

---

Give a recursive algorithm MATRIX-CHAIN-MULTIPLY(A, s, i, j) that actually performs the optimal matrix-chain multiplication, given the sequence of matrices [A1, A2, ..., An], the s table computed by MATRIX-CHAIN-ORDER, and the indices i and j. (The initial call would be MATRIX-CHAIN-MULTIPLY(A, s, 1, n).)

Answer

we should modify PRINT_OPTIMAL_PARENS.

MATRIX_CHAIN_MULTIPLY(A,s,i,j)
	if(i == j)
		return A[i]
	if(j == i+1)
		return A[i]*A[j];
	else
		B1 = MATRIX_CHAIN_MULTIPLY(A,s,i,S[i,j])
		B2 = MATRIX_CHAIN_MULTIPLY(A,s,S[i,j]+1,j)
		return B1*B2

Exercises 15.2-3

---

Use the substitution method to show that the solution to the recurrence (15.11) is Ω(2^n).

Answer

当n = 1时, 有p(n) = 1成立

假设对任意的k < n都成立,即p(k) >= c2^k,则有

因此,对于任意的c总有N0 = 1/c+1,使得当n > N0时, 有p(n) >= c2^n.

Exercises 15.2-4

---

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 MATRIX-CHAIN-ORDER. Show that the total number of references for the entire table is

(Hint: You may find equation (A.3) useful.)

Answer

Exercises 15.2-5

---

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

Answer

In our previous program,wt get ((A1(A2A3))((A4A5)A6)).

n = 6,and we have 5 parentheses.

A pair of parentheses musts contain a operator and n elements must have n-1 operators, so a full parenthesization of an n-element expression has exactly n-1 pairs of parentheses.

---

Follow @louis1992 on github to help finish this task.