Skip to content

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})