Exercise Lover

July 9, 2007

Exercises 15.3-2

Filed under: 15.2 — yuhanlyu @ 3:34 am

Since there is no subproblem overlap in the Mergesort.

Exercises 15.2-5

Filed under: 15.2 — yuhanlyu @ 3:25 am

If there are less than n-1 parentheses, then there must be at least one element has no parenthesis.

Exercises 15.2-4

Filed under: 15.2 — yuhanlyu @ 3:23 am

\sum_{l=2}^n (n-l+1)(l-1)2 = 2\sum_{l=1}^{n-1}(n-l)l = \frac{n^3 - n}{3}.

Exercises 15.2-3

Filed under: 15.2 — yuhanlyu @ 3:21 am

P(n) = \sum_{k=1}^{n-1} P(k)P(n-k). P(n+1) = \sum_{k=1}^{n} P(k)P(n+1-k). P(n+1) = \frac{2(2n+1)}{n+2}P(n). P(n) > T(n) which T(n) = 2T(n-1). Hence P(n) = \Omega(2^n).

Exercises 15.2-2

Filed under: 15.2 — yuhanlyu @ 3:13 am

Based on (15.12), it is easy to construct the recursive algorithm.

Exercises 15.2-1

Filed under: 15.2 — yuhanlyu @ 3:12 am

Blog at WordPress.com.