

Week 3 - Divide and Conquer

Assignment - Due 10/13/2018

Credit: source code of questions are from walkccc.

4.1-1

What does $\text{FIND-MAXIMUM-SUBARRAY}$ return when all elements of $A$ are negative?

4.1-2

Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in $\Theta(n^2)$ time.

4.1-3

Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?

4.2-1

Use Strassen's algorithm to compute the matrix product

$$\begin{pmatrix} 1 & 2 \\\\ 7 & 5 \end{pmatrix} \begin{pmatrix} 6 & 8 \\\\ 4 & 2 \end{pmatrix} .$$

Show your work.

4.2-2

Write pseudocode for Strassen's algorithm.

4.2-3

How would you modify Strassen's algorithm to multiply $n \times n$ matrices in which $n$ is not an exact power of $2$? Show that the resulting algorithm runs in time $\Theta(n^{\lg7})$.

4.3-1

Show that the solution of $T(n) = T(n - 1) + n$ is $O(n^2)$.

Assume $T(n) = O(n^2)$, then $\exists{c > 0}$ letting $T(n) \leq cn^2$:

$$\begin{align*} T(n) &= T(n - 1) + n \\ &\leq c(n - 1)^2 + n \\ &= c(n^2 - 2n + 1) + n \\ &= cn^2 + (1-2c)n + c \\ &\leq cn^2 \\ c &\geq 1 \text{ }(n \geq 1) \end{align*}$$

So, when $c \geq 1, n_0 = 1$, for all $n \geq n_0$ the inequality holds, which is

$$T(n) = T(n - 1) + n = O(n^2)$$

4.3-2

Show that the solution of $T(n) = T(\lceil n / 2 \rceil) + 1$ is $O(\lg n)$.

Assume $T(n) = O(\lg n)$, then $\exists{c > 0}$, letting $T(n) \leq c\lg(n-2)$:

$$\begin{align*} T(n) &= T(\bigg\lceil\dfrac{n}{2}\bigg\rceil) + 1 \\ &\leq T(\dfrac{n+2}{2}) + 1 \\ &\leq c\lg(\frac{n+2}{2} - 2) + 1 \\ &= c(\lg(n-2) - \lg{2}) + 1 \\ &= c\lg(n-2) - c + 1\\ &\leq c\lg(n-2) \\ c&\geq 1 \end{align*}$$

So, when $c \geq 1, n_0 = 1$, for all $n \geq n_0$ the inequality holds, which is

$$T(n) = T(\bigg\lceil\dfrac{n}{2}\bigg\rceil) + 1 = O(\lg n)$$

4.3-3

We saw that the solution of $T(n) = 2T(\lfloor n / 2 \rfloor) + n$ is $O(n\lg n)$. Show that the solution of this recurrence is also $\Omega(n\lg n)$. Conclude that the solution is $\Theta(n\lg n)$.

Assume $T(n) = \Theta(n\lg{n})$, then $\exists{c > 0, d > 0}$, letting $c(n+2)\lg{(n+2)} \leq T(n) \leq dn\lg{n}$:

$$\begin{align*} T(n) &= 2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + n & T(n) &= 2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + n\\ &\geq 2T(\frac{n-2}{2}) + n & &\leq 2T(\frac{n}{2}) + n \\ &\geq 2\times(\frac{c(n-2)}{2}+2)\lg{(\frac{n-2}{2}+2)} + n & &\leq 2\times\frac{dn}{2}\lg{\frac{n}{2}} + n\\ % &= c(n+2)(\lg{(n+2)} - \lg{2}) + n & &= dn(\lg{n} - \lg{2}) + n\\ &= c(n+2)\lg{(n+2)} + (1 - c)n - 2c & &= dn\lg{n} + (1 - d)n\\ &\geq c(n+2)\lg{(n+2)} & &\leq dn\lg{n} \\ 0 &< c \leq 1\text{ }(n \geq \dfrac{2c}{1-c}) & d &\geq 1\text{ }(n \geq 1) \end{align*}$$

So, when $0 < c \leq 1, d \geq 1, n_0 = \dfrac{2c}{1-c}$, for all $n \geq n_0$ the inequality holds, which is

$$T(n) = 2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + n = \Theta(n\lg{n})$$

4.3-5

Show that $\Theta(n\lg n)$ is the solution to the "exact" recurrence $\text{(4.3)}$ for merge sort.

The exact recurrence of Merge-Sort is

$$T(n) = T(\bigg\lceil \dfrac{n}{2}\bigg\rceil) + T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + \Theta(n)$$

So assume $T(n) = \Theta(n\lg{n})$, $\exists c > 0, \exists d > 0, \exists e > 0, \exists f > 0$ letting

$$c(n+2)\lg{(n+2)} \leq T(n) \leq e(n-2)\lg{(n-2)}$$

such that:

$$\begin{align*} T(n) &= T(\bigg\lceil\dfrac{n}{2}\bigg\rceil) + T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + \Theta(n) \\ &\geq 2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + \Theta(n) \\ &\geq 2T(\dfrac{n-2}{2}) + dn & \\ &\geq c(n+2)(\lg(n+2) - \lg2) + dn & \\ &= c(n+2)\lg(n+2) + (d-c)n - 2c & \\ &\geq c(n+2)\lg{(n+2)} & \\ % c &\geq \frac{c-d}{2}n \\ 0 &< c < d \text{ }(n \geq \dfrac{2c}{d-c}) & \\ \\ T(n) &= T(\bigg\lceil\dfrac{n}{2}\bigg\rceil) + T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + \Theta(n) \\ &\leq 2T(\bigg\lceil\dfrac{n}{2}\bigg\rceil) + \Theta(n) \\ &\leq 2T(\dfrac{n+2}{2}) + fn \\ &\leq e(n-2)(\lg(n-2) - \lg2) + fn\\ &= e(n-2)\lg(n-2) + (f-e)n + 2e \\ &\leq e(n-2)\lg{(n-2)} \\ 0&< f < e \text{ }(n \geq \dfrac{2e}{e-f}) \end{align*}$$

So, when $0 < c < d, 0 < f < e, n_0 = \max(\dfrac{2c}{d-c}, \dfrac{2e}{e-f})$, for all $n \geq n_0$ the inequality holds, which is

$$T(n) = T(\bigg\lceil\dfrac{n}{2}\bigg\rceil) + T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + \Theta(n) = \Theta(n\lg{n})$$