Introduction to Algorithms--Divide and Conquer

Posted on | In

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) + O(n)$

$T(n) = O(nlgn)$

$T(n) = 1T(n/2) + O(1)$

3. Powering a number

given a number $x$, integer $n\leq 0$>=0, compute $x^n$

Naive algorithm: multiply, time complexity: $O(n)$

$T(n) = T(n/2) + O(1) $

$T(n) = O(lgn)$

4. Fibonacci number

$F_n = 0$ , when n = 1

$F_n = 1$ , when n = 2

$ F_n = F_{n-1} + F_{n-2} $ , else

naive recursive algorithm: $\phi ^n$, $\phi = \frac{1+\sqrt{5}}{2}$, golden ratio, exponential time

  • Bottom-up algorithm

​ Compute $F_0, F_1, F_2..F_n$

​ Time complexity: $O(n)$

  • Naive recursive squaring

    $F_n = \phi_n / \sqrt{5}$ rounded to the nearest integer

    Time complexity: $O(lgn)$

    This method is unreliable, since floating-point arithmetic is prone to round-off errors (四舍五入时会有误差)

    NOT allowed

5. Recursive Squaring(Fibonacci number)

Theorem:

$$
\begin{bmatrix}
F_{n+1} & F_n\\
F_n & F_{n-1}
\end{bmatrix}^n
=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^n
$$
Time complexity: $O(lgn)$

proof: by induction on n

Base: (n=1)
$$
\begin{bmatrix}
F_2 & F_1\\
F_1 & F_0
\end{bmatrix}
=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^1
$$
Inductive step: (n>=2)
$$
\begin{equation}
\begin{split}
\begin{bmatrix}
F_{n+1} & F_n\\
F_n & F_{n-1}
\end{bmatrix}
&=
\begin{bmatrix}
F_n & F_{n-1}\\
F_{n-1} & F_{n-2}
\end{bmatrix}
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix} \\\\
&=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{n-1}
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}\\\\
&=
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^n
\end{split}
\end{equation}
$$

6. Matrix multiplication

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

Output: $C= [c_{ij}] = A \cdot B$

$c_{ij} = \sum_{k=1}^na_{ij}\cdot b_{kj}$

1
2
3
4
5
for i = 1 to n
	for j = 1 to n
		c_ij = 0
			for k = 1 to n 
				c_ij = c_ij + a_ik * b_kj

Time complexity: $O(n^3)$

IDEA

$n \times n$ matrix = $2 \times 2$ matrix of $n/2 \times n/2$ submatrices
$$
\begin{bmatrix}
r & s\\
t & u
\end{bmatrix}
=
\begin{bmatrix}
a & b\\
c & d
\end{bmatrix}
\cdot
\begin{bmatrix}
e & f\\
g & h
\end{bmatrix}
$$
$C= A\cdot B$
$$
\begin{equation}
\begin{split}
r &= ae + bg \\
s &= af + bh \\
t &= ce + dg \\
u &=cf + dh
\end{split}
\end{equation}
$$
8 mults of $(n/2) \times (n/2) $submatrices – recursive mult

4 adds of $(n/2) \times (n/2) $submatrices – $O(n^2)$

explanation for $n^2$: 

1
2
3
4
5
6
7
8
9
public static int[][] AddMatrix(int[][] p,int[][] q,int n){
	int[][] result = new int[n][n];
	for(int i=0;i<n;i++){
      	for(int j=0;j<n;j++){
        	result[i][j] = p[i][j]+q[i][j];
      	}
    }
  	return result;
}

Time complexity: $T(n) = 8T(n/2) + O(n^2) = O(n^3)$

No better than the ordinary algorithm

Strassen’s algorithm

IDEA: reduce # mults to 7

multiply $2 \times 2$ matrices with only 7 recursive mults
$$
\begin{equation}
\begin{split}
P_1 &= a \cdot (f - h) \\
P_2 &= (a + b) \cdot h \\
P_3 &= (c + d) \cdot e \\
P_4 &= d \cdot (g - e) \\
P_5 &= (a + d) \cdot (e + h) \\
P_6 &= (b - d) \cdot (g + h) \\
P_7 &= (a - c) \cdot (e + f)
\end{split}
\end{equation}
$$

$$
\begin{equation}
\begin{split}
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
\end{split}
\end{equation}
$$

Algorithm:

  • Divide: Partition A and B into $n/2 \times n/2$ submatrices. Form terms to be multiplied using + and -

    $P_1, P_2 …$ – $O(n^2)$

  • Conquer: Perform 7 multiplications of $n/2 \times n/2$ submatrices recursively

  • Combine: Form C using + and - on $n/2 \times n/2$ matrices $O(n^2)$

Time complexity: $T(n) = 7T(n/2) + O(n^2) = O(n^{lg7}) = O(n^{2.81})$

The number 2.81 may not seem much smaller than 3, but because the difference is in the exponent, the impact on running time is significant. In fact, Strassen’s algorithm beats the ordinary algorithm on today’s machines for $n\geq 32$ or so.

Best to date (of theoretical interest only): $O(n^{2.376..})$

7. VLSI layout (超大规模集成电路)

Problem: Embed a complete binary tree with n leaves in a grid using minimal area

Naive:

$H(n) = H(n/2) + O(1) = O(lgn)$

$W(n) = 2W(n/2) + O(1) = O(n)$

$Area = O(nlgn)$

递归式

递归式刻画分治算法的运行时间

3种求解递归式的方法：

  • 代入法
  • 递归树法，将递归式转换成为一棵树
  • 主方法：$T(n) = aT(n/b) + f(n)$, 生成 a 个子问题，每个子问题的规模是原问题规模的 1/b , 分解和合并步骤花费时间为 f(n)

Find maximum subarray, continuous

stock problem –> A[i] - A[i-1] –> find maximum subarray of A –> A[i..j]

Using divide and conquer, A[low..mid], A[mid+1..high]

Only three cases:

case 1: All in A[low..mid], so low<=i<=j<=mid

case 2: All in A[mid+1..high], so mid+1<=i<=j<=high

case 3: span over the mid, so low<=i<=mid<=j<=high

1
2
3
4
5
6
7
8
9
10
11
12
13
FIND-MAXIMUM-SUBARRAY(A, low, high)
if high==low
	return (low, high, A[low]) //base case: only one element
else 
	mid = (low+high)/2 --向下取整
	left-low, left-high, left-sum = FIND-MAXIMUM-SUBARRAY(A, low, mid)
	right-low, right-high, right-sum = FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
	cross-low, cross-high, cross-sum = FIND-MAXIMUM-CROSSING-SUBARRAY(A, low, mid, high)
	if left-sum>=right-sum and left-sum>=cross-sum
		return (left-low, left-high, left-sum)
	else if right-sum>=left-sum and right-sum>=cross-sum
		return (right-low, right-high, right-sum)
	else return cross-low, cross-high, cross-sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FIND-MAXIMUM-CROSSING-SUBARRAY(A, low, mid, high)
left-sum = -infinity
sum = 0
for i = mid downto low
	sum = sum + A[i]
	if sum > left-sum
		left-sum = sum
		max-left = i
right-sum = -infinity
sum = 0
for j = mid+1 downto high
	sum = sum + A[j]
	if sum > right-sum
		right-sum = sum
		max-right = j
return (max-left, max-right, left-sum+right-sum)

Running time: $ O(nlgn) $

Matrix Multiply – Strassen

1
2
3
4
5
6
7
8
9
SQUARE-MATRIX-MULTIPLY(A. B)
m = A.rows
let C be a new n*n matrix
for i = 1 to n
	for j  = 1 to n
	c_ij = 0
	for k = 1 to n
		c_ij = c_ij + a_ik * b_kj
return C

Time complexity: $O(n^3)$

Strassen

Time complexity: $O(n^{lg7}) = O(n^{2.81})$