Skip to content

Latest commit

 

History

History
63 lines (43 loc) · 2.32 KB

15.2.md

File metadata and controls

63 lines (43 loc) · 2.32 KB
Raw

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,则有

![](http://latex.codecogs.com/gif.latex?p\(n\) = \sum_{k=1}^{n-1}p(k)p(n-k) \ge \sum_{k=1}^{n-1}c2^kc2^{n-k} = c^2(n-1)2^n)

因此,对于任意的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

![](http://latex.codecogs.com/gif.latex?\\sum_{i=1}^{n}\\sum_{j=1}^{n}R\(i,j\)= \frac{n^3-n}{3})

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

Answer

![](http://latex.codecogs.com/gif.latex?\\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}l(n-l)= \frac{n^3-n}{3})

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.