Situation:
There is a problem P, input size n, solve it. (I am being silly here :)
Requirement:
The problem P should divisible in pieces that is significantly smaller than the original problem. This technique works fine if the divided pieces are close like n/2.
For example, to find n th fibonacci number, we can use the following recursive function
f_n = f_n-1 + f_n-2
We are dividing the original problem into size of n-1 and n-2. This ends up being an exponential algorithm.
If we make too many pieces divide and conquer might not work as well. Lets take example of multiplication of to n x n matrices, A and B. Naive algorithm would be of O(n ^ 3). We can divide the the A in 4 n/2 x n/2 matrices, and cand do the same with the other matrix B.
So, A = | a b | and B = | e f | result, C = A x B = | i j |
| c d | | g h | | k l |
where, a, b, c, ... are all n/2 x n/2 matrices
i = a * e + b * g
j = a * f + b * h
so on and so forth.
to compute i, we need to n/2 x n/2 matrix multiplication and then addition. There are O(n ^ 2) elements in the matrix so addition would be of O(n ^ 2). So to compute, i, the order would be 2 T(n/2) + O(n ^ 2)
That means the order of C's computation would be T(n) = 8 T(n/2) + O(n^2). Using master method this ends up being T(n) = O(n^3). The problem here is we divided in too many parts(8) and it ended up doing no good. We still have O(n^3).
Steps
Divide and conquer has 3 steps.
0. Divide : Break the input in parts.
1. Conquer : Compute on each divided parts and find result for those smaller parts.
2. Combine : Find solution for the bigger problem by combining the smaller part's solutions.
Examples
0. Binary search
Problem: a sequence of numbers A = a, b, c, d, .... where a < b < c < d ..... Check if an element x is present in the sequence
Divide:
Divide A in two sequences B and C such that size of B and C is n/2.
Conquer: If x == A[n/2] then return true. If x < A[n/2], then look in B else look in C
Combine: Nothing to combine
1. Peak finding
In a sequence, a, p, b, an element p is peak iff p >= a and p >= b.
Problem: given a sequence of numbers A = a, b, c, d, ... The elements of A are not sorted. Find a peak in this sequence.
Divide: Divide the sequence A in two equal sequences, B and C.
Conquer: if A[n/2] is a peak then return. Else, Take the Part that has the element that did not let A[n/2] to become a peak.
Combine: nothing to combine.
2D version
A is a n x n matrix.
Divide: Divide A in two n x (n / 2) matrices
Conquer: take mid = A[n/2] which is n x 1 matrix. With linear search find the global maxima of mid.
if it is a peak, return.
Else take the half of A that did not let global max of mid to become a peak.
2. Merge sort
Problem: an array A = [a, b, c, d, ... n elements]. elements are not sorted. Find a permuation of elements of A, [a', b', c', ...] such that a' < b' < c' < .. so on and so forth.
Divide : Divide A into two halves B and C where B and C both has n/2 elements.
Conquer :
Combine : Merge two sorted Array B' and C' and return the result.
3. Finding power x ^ n
problem: given x and n find x * x * x ..... * x (n times)
naive algorithm: O(n)
Divide:
x ^ n = x ^ (n/2) * x ^ (n/2)
Divide computation to compute x ^ (n/2)
Conquer:
Combine: we have result of a = x ^ (n/2). multiply the result with it self (i.e a * a) and return the result
T(n) = T(n/2) + 1 = O(log n)
code:
def comute_power(x, n):
if(n == 0):
return 1
if(n % 2 == 0):
a = compute(x, n/2)
return a * a
else:
a = compute(x, (n-1)/2)
return a * a * x
4. Finding nth Fibonacci number
The naive algorithm to find fibonacci number at the beginning of this article is an exponential algorithm. It is possible to compute fibonacci number in O(n) using dynamic programming. We will discuss here how we can find nth fibonacci number in O(log n) time. nth fibonacci number can be found using obtaining nth power of a special 2 x 2 matrix.
| f_n+1 f_n | | 1 1 |
| | = | | to the power n (theorem 1)
| f_n f_n-1 | | 1 0 |
exponentiation can be done in (log n) time for a constant sized matrix. theorem 1 can be proved easily using induction.
5. Matrix multiplication
In the beginning of this article we saw how dividing a problem in too many sub problems we were unable to find a better solution. Strassen developed an algorithm[2] that would to 7 matrix multiplication instead of 8. then the T(n) = 7 * T(n/2) + O(n ^ 2) ~ )(n ^ 2.83)
6. VLSI layout
connect n grid without overlapping wires. make sure the area of the circuit board is as small as possible. Figure 1 shows connection of the grids in a binary tree fashion. Lets say height = h and width = w. from the figure,
h(n) = h(n/2) + 1 = O(logn)
w(n) = 2 * w(n/2) + 1 = O(n)
area = h * w = O(n * logn)
we can do better. The smallest we can make the area is n because we need to put those n grids anyway.
if we can make h~O(sqrt(n)) and w~O(sqrt(n)) then area would be O(n)
from master method we know O(sqrt(n)) = 2 T(n/4) + O(n ^ (1/2 - epsilon)). We need to divide the n grids in n/4 sized groups as shown in figure 2. Then,
h(n) = 2 * h(n/4) + 1 = O(sqrt (n))
w(n) = 2 * w(n/4) + 1 = O(sqrt(n))
area = O(sqrt(n) * sqrt(n)) = O(n)
7. Quicksort
Divide: divide array A in two parts around a pivot.
A = | <= pivot | pivot | > pivot |
Conquer: recursively divide
combine: nothing to do
algorithm:
def partition(A, p, q): #A is array, p start and q is end index. returns position of pivot
pivot = A[p] # chooose first element as pivot
pivot_index = p # all element from (pivot_index - 1) to -infinity are less than or equal to pivot
for i in range(p+1, q):
if A[i] <= pivot: # element less than or equal to pivot, we need to put it on left side
A[i], A[pivot_index] = A[pivot_index], A[i]
pivot_index += 1
A[p], A[pivot_index-1] = A[pivot_index-1], A[p] #swap
return pivot_index-1
def quicksort(A, p, q):
if p <= q:
return A
pivot_index = partition(A, p, q)
quicksort(A, p, pivot_index-1)
quicksort(A, pivot_index+1, q)
A = [0, 2, 1, -1]
quicksort(A, 0, 4)
Analysis: worst case, T(n) = T(n-1) + n = O(n ^ 2)
Avgcase T(n) = T(n/d) + T((n * (d-1)) / d) + O(n) = O(n logn)
If pivot is randomly chosen, Worst case, T(n) = O(n logn)
8. Order statistics
Problem: There is an array A, find the kth order element of the array
if k = 1, smallest element
if k = n, max element
Divide:
def partition(A, p, q): # p start index, q end index
pivot = A[p]
i = p + 1
for k in range(i, q):
if A[k] <= pivot:
A[i], A[k] = A[k], A[i]
i += 1
i -= 1
A[p], A[i] = A[i], A[p]
return i
def search(A, p, q, k): # kth order element to find
if p >= q:
if p == k:
return A[p]
pivot_index = partition(A, p, q)
if pivot_index == k:
return A[k]
if pivot_index > k:
return search(A, p, pivot_index - 1, k)
else
return search(A, pivot_index + 1, q, k)
On average case, T(n) = T(n/2) + O(n) = O(n)
If pivot is randomly chosen, the above algorithm is O(n) even in worst case.
There is another example of computing square root can be found here http://www.saifulabu.me/2017/08/benefit-of-divide-and-conquer.html
Reference:
0. MIT OCW 6.006 introduction to algorithms
1. MIT OCW 6.046j lecture on divide and conquer
2. http://www.geeksforgeeks.org/strassens-matrix-multiplication/
There is a problem P, input size n, solve it. (I am being silly here :)
Requirement:
The problem P should divisible in pieces that is significantly smaller than the original problem. This technique works fine if the divided pieces are close like n/2.
For example, to find n th fibonacci number, we can use the following recursive function
f_n = f_n-1 + f_n-2
We are dividing the original problem into size of n-1 and n-2. This ends up being an exponential algorithm.
If we make too many pieces divide and conquer might not work as well. Lets take example of multiplication of to n x n matrices, A and B. Naive algorithm would be of O(n ^ 3). We can divide the the A in 4 n/2 x n/2 matrices, and cand do the same with the other matrix B.
So, A = | a b | and B = | e f | result, C = A x B = | i j |
| c d | | g h | | k l |
where, a, b, c, ... are all n/2 x n/2 matrices
i = a * e + b * g
j = a * f + b * h
so on and so forth.
to compute i, we need to n/2 x n/2 matrix multiplication and then addition. There are O(n ^ 2) elements in the matrix so addition would be of O(n ^ 2). So to compute, i, the order would be 2 T(n/2) + O(n ^ 2)
That means the order of C's computation would be T(n) = 8 T(n/2) + O(n^2). Using master method this ends up being T(n) = O(n^3). The problem here is we divided in too many parts(8) and it ended up doing no good. We still have O(n^3).
Steps
Divide and conquer has 3 steps.
0. Divide : Break the input in parts.
1. Conquer : Compute on each divided parts and find result for those smaller parts.
2. Combine : Find solution for the bigger problem by combining the smaller part's solutions.
Examples
0. Binary search
Problem: a sequence of numbers A = a, b, c, d, .... where a < b < c < d ..... Check if an element x is present in the sequence
Divide:
Divide A in two sequences B and C such that size of B and C is n/2.
Conquer: If x == A[n/2] then return true. If x < A[n/2], then look in B else look in C
Combine: Nothing to combine
1. Peak finding
In a sequence, a, p, b, an element p is peak iff p >= a and p >= b.
Problem: given a sequence of numbers A = a, b, c, d, ... The elements of A are not sorted. Find a peak in this sequence.
Divide: Divide the sequence A in two equal sequences, B and C.
Conquer: if A[n/2] is a peak then return. Else, Take the Part that has the element that did not let A[n/2] to become a peak.
Combine: nothing to combine.
2D version
A is a n x n matrix.
Divide: Divide A in two n x (n / 2) matrices
Conquer: take mid = A[n/2] which is n x 1 matrix. With linear search find the global maxima of mid.
if it is a peak, return.
Else take the half of A that did not let global max of mid to become a peak.
2. Merge sort
Problem: an array A = [a, b, c, d, ... n elements]. elements are not sorted. Find a permuation of elements of A, [a', b', c', ...] such that a' < b' < c' < .. so on and so forth.
Divide : Divide A into two halves B and C where B and C both has n/2 elements.
Conquer :
Combine : Merge two sorted Array B' and C' and return the result.
3. Finding power x ^ n
problem: given x and n find x * x * x ..... * x (n times)
naive algorithm: O(n)
Divide:
x ^ n = x ^ (n/2) * x ^ (n/2)
Divide computation to compute x ^ (n/2)
Conquer:
Combine: we have result of a = x ^ (n/2). multiply the result with it self (i.e a * a) and return the result
T(n) = T(n/2) + 1 = O(log n)
code:
def comute_power(x, n):
if(n == 0):
return 1
if(n % 2 == 0):
a = compute(x, n/2)
return a * a
else:
a = compute(x, (n-1)/2)
return a * a * x
4. Finding nth Fibonacci number
The naive algorithm to find fibonacci number at the beginning of this article is an exponential algorithm. It is possible to compute fibonacci number in O(n) using dynamic programming. We will discuss here how we can find nth fibonacci number in O(log n) time. nth fibonacci number can be found using obtaining nth power of a special 2 x 2 matrix.
| f_n+1 f_n | | 1 1 |
| | = | | to the power n (theorem 1)
| f_n f_n-1 | | 1 0 |
exponentiation can be done in (log n) time for a constant sized matrix. theorem 1 can be proved easily using induction.
5. Matrix multiplication
In the beginning of this article we saw how dividing a problem in too many sub problems we were unable to find a better solution. Strassen developed an algorithm[2] that would to 7 matrix multiplication instead of 8. then the T(n) = 7 * T(n/2) + O(n ^ 2) ~ )(n ^ 2.83)
6. VLSI layout
connect n grid without overlapping wires. make sure the area of the circuit board is as small as possible. Figure 1 shows connection of the grids in a binary tree fashion. Lets say height = h and width = w. from the figure,
h(n) = h(n/2) + 1 = O(logn)
w(n) = 2 * w(n/2) + 1 = O(n)
area = h * w = O(n * logn)
we can do better. The smallest we can make the area is n because we need to put those n grids anyway.
if we can make h~O(sqrt(n)) and w~O(sqrt(n)) then area would be O(n)
from master method we know O(sqrt(n)) = 2 T(n/4) + O(n ^ (1/2 - epsilon)). We need to divide the n grids in n/4 sized groups as shown in figure 2. Then,
h(n) = 2 * h(n/4) + 1 = O(sqrt (n))
w(n) = 2 * w(n/4) + 1 = O(sqrt(n))
area = O(sqrt(n) * sqrt(n)) = O(n)
7. Quicksort
Divide: divide array A in two parts around a pivot.
A = | <= pivot | pivot | > pivot |
Conquer: recursively divide
combine: nothing to do
algorithm:
def partition(A, p, q): #A is array, p start and q is end index. returns position of pivot
pivot = A[p] # chooose first element as pivot
pivot_index = p # all element from (pivot_index - 1) to -infinity are less than or equal to pivot
for i in range(p+1, q):
if A[i] <= pivot: # element less than or equal to pivot, we need to put it on left side
A[i], A[pivot_index] = A[pivot_index], A[i]
pivot_index += 1
A[p], A[pivot_index-1] = A[pivot_index-1], A[p] #swap
return pivot_index-1
def quicksort(A, p, q):
if p <= q:
return A
pivot_index = partition(A, p, q)
quicksort(A, p, pivot_index-1)
quicksort(A, pivot_index+1, q)
A = [0, 2, 1, -1]
quicksort(A, 0, 4)
Analysis: worst case, T(n) = T(n-1) + n = O(n ^ 2)
Avgcase T(n) = T(n/d) + T((n * (d-1)) / d) + O(n) = O(n logn)
If pivot is randomly chosen, Worst case, T(n) = O(n logn)
8. Order statistics
Problem: There is an array A, find the kth order element of the array
if k = 1, smallest element
if k = n, max element
Divide:
def partition(A, p, q): # p start index, q end index
pivot = A[p]
i = p + 1
for k in range(i, q):
if A[k] <= pivot:
A[i], A[k] = A[k], A[i]
i += 1
i -= 1
A[p], A[i] = A[i], A[p]
return i
def search(A, p, q, k): # kth order element to find
if p >= q:
if p == k:
return A[p]
pivot_index = partition(A, p, q)
if pivot_index == k:
return A[k]
if pivot_index > k:
return search(A, p, pivot_index - 1, k)
else
return search(A, pivot_index + 1, q, k)
On average case, T(n) = T(n/2) + O(n) = O(n)
If pivot is randomly chosen, the above algorithm is O(n) even in worst case.
There is another example of computing square root can be found here http://www.saifulabu.me/2017/08/benefit-of-divide-and-conquer.html
Reference:
0. MIT OCW 6.006 introduction to algorithms
1. MIT OCW 6.046j lecture on divide and conquer
2. http://www.geeksforgeeks.org/strassens-matrix-multiplication/
No comments:
Post a Comment