Divide and Conquer

Divide and Conquer

The divide-and-conquer design paradigm

1. Divide the problem (instance) into subproblems.
2. Conquer the subproblems by solving them recursively.
3. Combine subproblem solutions.

EXAMPLE:

1. Merge sort \(T(n)=2T(n/2)+\Theta(n)\Rightarrow T(n)=\Theta(n\lg n)\)​

2. Binary search \(T(n)=T(n/2)+\Theta(1)\Rightarrow T(n)=\Theta(\lg n)\)

3. Powering a number \(T(n)=T(n/2)+\Theta(1)\Rightarrow T(n)=\Theta(\lg n)\)

Computing Fibonacci numbers

Theorem: \[ \begin{equation} \begin{bmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\\ \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0\\ \end{bmatrix}^n \end{equation} \] \(T(n)=\Theta(\lg n)\)

Matrix multiplication

Standard algorithm

for i ← 1 to n
	do for j ← 1 to n
		do cᵢⱼ ← 0
			for k ← 1 to n
				do cᵢⱼ ← cᵢⱼ + aᵢₖbₖⱼ

\(T(n)=\Theta(n^3)\)

Divide-and-conguer algorithm

\[ \begin{equation} \begin{bmatrix} r & s\\ t & u\\ \end{bmatrix} = \begin{bmatrix} a & b\\ c & d\\ \end{bmatrix} \begin{bmatrix} e & f\\ g & h\\ \end{bmatrix} \end{equation} \]

\[ \begin{equation} \left\{ \begin{array}{c} r=ae+bg\\ s=af+bh\\ t=ce+dg\\ u=cf+dh \end{array} \right. \end{equation} \]

\(T(n)=8T(n/2)+\Theta(n^2)\Rightarrow T(n)=\Theta(n^3)\)

conclusion: No better than the ordinary algorithm

Strassen's idea

• Multiply 2x2 matrices with only 7 recursive mults.

\[ \begin{equation} \begin{array}{c} P_1=a(f-h) & r=P_5+P_4-P_6\\ P_2=(a+b)h & s=P_1+P_2\\ P_3=(c+d)e & t=P_3+P_4\\ P_4=d(g-e) & u=P_5+P_1-P3+P_7\\ P_5=(a+d)(e+h) & \framebox{7 muts. 18 adds/subs}\\ P_6=(b-d)(g+h) & \color{red}{Note:}\text{ No reliance on} \\ P_7=(a-c)(e+f) & \text{commutativity of mult!}\\ \end{array} \end{equation} \]

\(T(n)=7T(n/2)+\Theta(n^2)\Rightarrow T(n)=\Theta(n^{\lg 7})\)