Tuesday, 11 March 2014

Divide-and-Conquer Algorithms


A divide-and-conquer algorithm
  • Derives the output directly, for small instances
  • Divides large instances to smaller ones, and (recursively) applies the algorithm on the smaller instances.
  • Combines the solutions for the subinstances, to produce a solution for the original instance.

Merge Sort

Sets of cardinality greater than one are decomposed into two equal subsets, the algorithm is recursively invoked on the subsets, and the returned ordered subsets are merged to provide a sorted variant of the original set.
The time complexity of the algorithm satisfies the recurrence equation
      {
T(n) =  2T(n/2)+ O(n)  if n > 1
        0              if n = 1
whose solution is T(n) = O(n log n).

Quick Sort

Sets of cardinality greater than one are partitioned into two subsets, and then the algorithm is recursively invoked on the subsets. The partitioning uses a key from the set as a pivot. Values smaller than the pivot are sent to one subset, and values greater than the pivot are sent to the other subset.
For randomly chosen pivots, the expected running time of the algorithm satisfies the recurrence equation
      { 2T(n/2)+ O(n)  if n > 1
T(n) =  0              if n = 1
whose solution is T(n) = O(n log n). The worst case time complexity of the algorithm is O(n2).

Tiling with L-Grouped Tiles

The problem is to tile a board of size 2k × 2k with one single tile and 22k 1 L-shaped groups of 3 tiles. A divide-and-conquer approach can recursively divide the board into four, and place a L-grouped set of 3 tiles in the center at the parts that have no extra tile.
|---------------|
|               |
|               |
|               |
|               |
|               |
|               |
----------------|---------------|
|               |
|               |
|               |
|   ||          |
|               |
|               |
----------------
|-------|-------|
|       |       |
|       |       |
|-----||||------|
|   ||  |       |
|       |       |
|       |       |
----------------|---|---|---|---|
| ||||  | ||||  |
----|-------|---|
|---|-||||--|---|
| ||||  |   ||  |
----|-------|---|
|   |   |   |   |
----------------

Closest Pair

Given a set of points (xi, yi) the problem asks what is the distance between the two closest points. A brute force approach in which the distances for all the pairs are measured takes O(n2) time.
A divide-and-conquer algorithm can sort the points along the x-axis, partition the region into two parts Rleft and Rright having equal number of points, recursively apply the algorithm on the sub-regions, and then derive the minimal distance in the original region.
The closest pair resides in the left region, the right region, or across the borderline. The last case needs to deal only with points at distance d = min(dleftdright) from the dividing line, where dright and dright are the minimal distances for the left and right regions, respectively.
|-----------------
|      ##|# •    |
|•     #•|#    • |
|      ##•#  •   |
|    • #•|#      |
|  •   ##|#   •  |
|      #•|#•     |
------------------
The points in the region around the boundary line are sorted along the coordinate, and processed in that order. The processing consists of comparing each of these points with points that are ahead at most d in their ycoordinate. Since a window of size d × 2d can contain at most 6 points, at most five distances need to be evaluated for each of these points.
The sorting of the points along the and coordinates can be done before applying the recursive divide-and-conquer algorithm; they require O(n log n) time.
The processing of the points along the boundary line takes O(n) time. Hence, the recurrence equation for the time complexity of the algorithm:
      { 2T(n/2)+ O(n)  if n > 1
T(n) =  0              if n = 1
The solution of the equation is T(n) = O(n log n).

Strassen’s Matrix Multiplication

Given: Two N by N matrices A and B.
Problem: Compute × B

Brute Force

for i:= 1 to N do 
  for j:=1 to N do 
     C[i,j] := 0; 
     for k := 1 to N do 
        C[i,j] := C[i,j] + A[i,k] * B[k,j] 
O(N3) multiplications

Divide and Conquer

[        ]   [        ]   [        ]
 C11  C12  =  A11  A12  ×  B11  B12
 C21  C22     A21  A22     B21  B22
 P  = (A  + A  )(B   + B  )
  1     11   22   11   22
 P2 = (A21 + A22)B11
 P3 = A11(B12- B22)
 P4 = A22(B21- B11)
 P  = (A  + A  )B
  5     11   12  22
 P6 = (A21- A11)(B11 + B12)
 P7 = (A12- A22)(B21 + B22)
C11 = P1 + P4 - P5 + P7
C   = P + P
  12    3   5
C21 = P2 + P4
C22 = P1 + P3 - P2 + P6
From
      { 7T(n/2)+ cn  if n > 1
T(n) =  c            if n = 1
T(n) = O(nlog 7) = O(n2.81).
Best known upper bound is n2.376

No comments:

Post a Comment

 

FACEBOOK PAGE

SKETCHES & PAINTINGS