# MIT Algorithms (2)

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)
^           [email protected]____________
|           |                        |
|     [email protected]_______           [email protected]_______
|     |            |           |            |
|   [email protected]__        [email protected]__       [email protected]__        [email protected]__
|   |   |        |   |       |   |        |   |
|   @   @        @   @       @   @        @   @
|-------------------------------------------------> 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)
^
|
|   @     @             @     @
|   |     |             |     |
|   @[email protected]@             @[email protected]@
|   |  |  |             |  |  |
|   @  |  @             @  |  @
|      |                   |
|      @[email protected]@
|      |                   |
|   @  |  @             @  |  @
|   |  |  |             |  |  |
|   @[email protected]@             @[email protected]@
|   |     |             |     |
|   @     @             @     @
|-----------------------------------> L(n)
0
L(n) = 2 * L(n/4) + θ(1)
= Θ(√n)
(Case 1)

声明: 本文为0xBBC原创, 转载注明出处喵～