Introduction to Algorithms/Divide-and-Conquer Algorithm

Video Link

1. Divide the problem (instance) into one or more subproblems
2. Conquer each subproblem recursively
3. Combine solutions

Running time (merge sort):

\[T(n)=2T\left( \frac{n}{2} \right)+\Theta(n)\]

case2: $T(n)=n\log n$.

Binary search

find $x$ in sorted array– 1. Divide: compare $x$ with middle 2. Conquer: recurse in one subarray 3. Combine: trival

\[T(n)=2T\left( \frac{n}{2} \right)+\Theta(1)\]

Powing a number

given number $x$, integer $n \geqslant 0$, compute $x^n$ –

\[x^n =\begin{cases} x^{n/2} \cdot x^{n/2} &\text{if} \, n \, \text{even} \newline x^{\frac{n-1}{2}} \cdot x^{\frac{n-1}{2}} &\text{if} \, n \,\text{odd} \end{cases}\]

Fibonacci numbers

bottom-up: compute $F_{0},F_{1},F_{2},\dots,F_{n}$ . $\Theta(n)$

Naive recursive squaring: (not allowed)

\[F_{n} = \left[\frac{\psi^n}{\sqrt{ 5 }}\right]\]

Right recursive squaring:

Thm:

\[\begin{bmatrix} F_{n+1} & F_{n} \newline F_{n} & F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \newline 1 & 0 \end{bmatrix}^n\]

Proof: by induction on $n$

Base: trival.

Step:

\[\begin{bmatrix} F_{n+1} & F_{n} \newline F_{n} & F_{n-1} \end{bmatrix} = \begin{bmatrix} F_{n} & F_{n-1} \newline F_{n-1} & F_{n-2} \end{bmatrix} \begin{bmatrix} 1 & 1 \newline 1 & 0 \end{bmatrix}\]

Matrix multiplication

Input: $A=[a_{ij}],B=[b_{ij}]$

Output: $C = [c_{ij}] =AB,i,j=1,\dots,n$

standard alg is $\Theta (n^3)$

Divide and conquer alg:

• Idea: $n\times n$ matrix = $2 \times 2$ block matrix of $\frac{n}{2} \times \frac{n}{2}$ submatrix

\[\begin{bmatrix} r & s \newline t & u \end{bmatrix} =\begin{bmatrix} a & b \newline c & d \end{bmatrix} \cdot \begin{bmatrix} e & f \newline g & h \end{bmatrix}\] \[r=ae+bg\] \[s=af+bh\] \[t=ce+dg\] \[u=bf+dh\]

8 recursive mults of $\frac{n}{2} \times \frac{n}{2}$ submatrix and 4 add.

\[T(n)=8T\left( \frac{n}{2} \right)+\Theta(n^2)\]

that’s case 1 and no better.

Strassen’s algorithm

Idea: reduce # mults.

\[p_{1}=a(f-h)\] \[p_{2}=(a+b)h\] \[p_{3}=(c+d)e\] \[p_{4}=d(g-e)\] \[p_{5}=(a+d)(e+h)\] \[p_{6}=(b-d)(g+h)\] \[p_{7}=(a-c)(e+f)\] \[r=p_{5}+p_{4}-p_{2}+p_{6}\] \[s=p_{1}+p_{2}\] \[t=p_3+p_{4}\] \[u=p_{5}+p_{1}-p_{3}-p_{7}\] \[T(n)=7T\left( \frac{n}{2} \right)+\Theta(n^2)=\Theta(n^{\lg 7})\]

VLSI(very large-scale integration) layout

Problem: embed a complete binary tree on $n$ leaves in a grid with minimum area.

\[H(n)=H\left( \frac{n}{2} \right)+\Theta(1)=\Theta(\lg n)\] \[W(n)=2W\left( \frac{n}{2} \right)+O(1)=\Theta(n)\] \[A(n)=H(n)W(n)=n\lg n\]

Goal: $W(n)=\Theta(\sqrt{ n }),H(n)=\Theta(\sqrt{ n }) \implies A(n)=\Theta(n)$

\[T(n)=2T(\frac{n}{4})+O(n^{1/2-\epsilon})\]