1) Divide and conquer
1. Divide
divide the problem (instance) into one or more subproblems
2. Conquer
conquer each problem recursively
3. Combine
2) Merge sort
1. divide into 2 halves
2. recursively sort each subarray
3. to combine the solution
4. merge
3) Running time
T(n) = 2 * T(n/2) + θ(n)
(n/2) : the size of the subproblem
2 : the number of the problems
n : extra work (divide and conquer time in this case)
a = 2
b = 2
f(n) = n
k = 0
f(n) = nlogb(a) = nlog2(2) = n
so, this is Case 2.
θ(nlgn)
4) Binary search
find x in an array
1. compare x with middle
2. conquer: recurse in one subarray
3. combine
T(n) = T(n/2) + θ(1)
a = 1
b = 2
f(n) = 1
Case 1:
O(lgn)
5) Powering a number
given number x, integer n >= 0, compute xn
Naive algorithm:
O(n) time
Divide-and-conquer algo:
xn= x(n/2) * x(n/2) if n ever
xn= x((n-1)/2) * x((n-1)/2) *x if n odd
T(n) = T(n/2) + θ(1)
= O(lgn)
5) Fiboinacci Numbers
F(n) :
0 if n = 0
1 if n = 1
F(n-1) + F(n-2) if n >= 2
Naive algorithm:
Time SL(φn), φ=(1+√5)/2
Exponential time, but we want polynomial time
Divide-and-conquer algo: (bottom-up)
compute F0, F1, F2, ..., Fn
Time: θ(n)
but it is not the best still
Naive recursive squaring algorithm:
Fn = φn/√5 round it to the nearest integer
Time: O(lgn)
(but it cannot be done in real machine)
Right recursive squaring algorithm:
Thm: Fn = [(1 1),(1 0)]n
= [(F(n-1) F(n)),(F(n) F(n-1))]n
Time: O(lgn)
Proof by induction on n:
Base:
[(1 1),(1,0)]1 = [(F(2),F(1)),(F(1),F(0))]
Step:
[(F(n+1) F(n)),(F(n) F(n-1))]
=[(F(n) F(n-1)),(F(n-1) F(n-2))] * [(1 1),(1,0)]
=[(1 1),(1,0)](n-1) * [(1 1),(1,0)]
=[(1 1),(1,0)]n
6) Matrix multiplication
Input A=[aij], B=[bij]
Output C=[cij] = A * B
Cij = the inner product of the ith row of A with the jth colume of B
Standard alg: Time θ(n3)
for i<-1 to n
do for j<-1 to n
do for k<-1 to n
do cij<-0 + aij * bkj
Divide-and-conquer alg:
idea:
n x n matrix
=2 x 2 block matrix of n/2 x n/2 sub matrix
--------------- ________________ ________________
| r | s | | a | b | | e | f |
| | | | | | | | |
|-------------- = ---------------- + ----------------
| t | u | | c | d | | g | h |
|_____________| |______________| |______________|
C A B
r = a * e + b * g
s = a * f + b * h
t = c * e + d * g
u = c * f + d * h
8 recurensive mults of n/2 x n/2 matrix
Time: T(n) = 8 * T(n/2) + θ(n2)
a = 8
b = 2
f(n) = n2
f(n) < nlogb(a) = n3
Case 1:
T(n) = θ(n3)
Strassen's algorithm:
idea:
reduce number of mults
-> 7
P1 = a * (f-h)
P2 = (a+b) * h
P3 = (c+d) * e
P4 = d * (g-e)
P5 = (a+d) * (e+h)
P6 = (b-d) * (g+h)
P7 = (a-c) * (e+f)
r = P5 + P4 - P2 + P6
s = P1 + P2
t = P3 + P4
u = P5 + P1 - P3 - P7
check:
u = P5 + P1 - P3 - P7
= (a*e + a*h + d*e + d*h) + (a*f - a*h) - (c*e + d*e) - (a*e + a*f - c*e - c*f)
= d*h + c*f
1. Divide
divide A, B
compute terms for products θ(n2)
2. conquer recursively compute P1, P2, ... , P7
3. combine r,s,t,u
T(n) = 7 * T(n/2) + θ(n2)
a = 7
b = 2
f(n) < nlog2(7)
Case 1:
θ(nlog2(7)) = O(n2.81)
7) VLSI layout
Problem, Embed a complete binary tree into some chip layout on a grid
Let's say it has n leaves. I want to imbed it into a grod with minimum area.
Naive embedding:
H(n)
^ _____________@____________
| | |
| ______@_______ ______@_______
| | | | |
| __@__ __@__ __@__ __@__
| | | | | | | | |
| @ @ @ @ @ @ @ @
|-------------------------------------------------> W(n)
0
H(n) = H(n/2) + θ(1)
= θ(lgn)
W(n) = 2 * W(n/2) + O(1)
= θ(n)
area = θ(nlgn)
Goal:
W(n) = θ(√n)
H(n) = θ(√n)
area = θ(n)
then it should be T(n) = 2 * T(n/4) + O(n(1/2-ε))
so, we have to layout:
L(n)
^
|
| @ @ @ @
| | | | |
| @--@--@ @--@--@
| | | | | | |
| @ | @ @ | @
| | |
| @---------@---------@
| | |
| @ | @ @ | @
| | | | | | |
| @--@--@ @--@--@
| | | | |
| @ @ @ @
|-----------------------------------> L(n)
0
L(n) = 2 * L(n/4) + θ(1)
= Θ(√n)
(Case 1)