Divide and Conquer

1. The Divide and Conquer Paradigm:
  a) Divide into smaller sub-problems.
  b) Conquer via recursive calls.
  c) Combine solutions to sub-problems into one for the original problem
 
2. The definition of inversions counting problem:
Input : Array A containing the numbers 1, 2, 3, ... , n in some arbitrary order.
Output: The number of inversions = the number of pairs(i,j) of array indeices with i < j and A[i]>a[j]
Motivation: Numerical similarity measurement between two ranked lists.

3. Examples: (1, 3, 5, 2, 4, 6)
   Inversions: (3, 2) , (5, 2) , (5, 4)
  

 
4. Divide and Conquer solution for inversions counting:
 inversion (i,j) [wth i <j] :
 
 left ---- if i, j <= n/2
 right ---- if i, j > n/2
 split ---- if i <= n/2 <j
 
 Count ( arry A, length n)
 if n = 1 return 0
 else
       x = Count(1st half of A, n/2)
       y = Count(2nd half of A, n/2)
       z = CountSplitInv( A , n )
 return x + y + z
 
5. Key idea of CountSplitInv :
   have recursive calls both count inversions and sort
   Motivation: Merge sub-routine natually uncovers split inversions:
  
6. The split inversions involving an element y of the 2nd array C are precisely the numbers left in the 1st array B when y is copied to the output D.
   Merge_and_CountSplitInv
   -- while merging the two sorted sub-arrays, keep counting total number of split inversions.
   -- When element of 2nd array C gets copied to output D, increment the total nunmber of conversions by the number of lements remaining in the 1st array B.

7. Naive Divide and Conquer solution for matrix multiplication:
  ( a b ) ( e f ) = ( ae + bg af + bh) 
  ( c d ) ( g h ) = ( ce + dg cf + dh)
 
  T(n) = 8T(n/2) + n^2 = O(n^3)

8. Strassen’s Algorithm
  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)
  ( a b ) ( e f ) = ( P5+P4-P2+P6 P1+P2) 
  ( c d ) ( g h ) = ( P3+P4 P1+P5-P3-P7)
  Totally 7 sub-problems.
 
9. The definition of Closest Pair problem:
Input: a Set P = { p1, p2, ..., pn} of n points in the Plane.
Output: a pair p*, q* of P and such that p*, q* are distinct and d(p*,q*) is minimum over any pair p,q of P ( d(p,q) is Euclidean distance of p and q)

10. Solution to 1-D version of Closest Pair:
  a) sort the points ( O(n log n)
  b) return closest pair of adjacent points (O(n))

11. Divide and Conquer solution to ClosestPair(P) :
  a) Let Q = left half of P , R = right half of P
  b) (p1, q1) = ClosestPair(Q)
  c) (p2, q2) = ClosestPair(R)
  d) s = min { d(p1, q1) , d(p2, q2) }
  d) (p3, q3) = ClosestSplitPair(P , s)
  e) return closest of (p1, q1) , (p2, q2) , (p3, q3)

12. Solution to ClosestSplitPair(P, s)
  a) Let x0 = biggest x-coordinate in left of P.
  b) Let Sy = points of P with x-coordinate in [x0-s , x0 + s], sorted by y-coordinate  
  c) Initialize best = m , bestPair = NULL
     for i = 1 to |Sy|-1
       for j = 1 to min {7, |Sy|-i}
         Let p, q the ith and jth points of Sy
         if d(p,q) < best
           bestPair = (p, q) , best = d(p,q)
 
  Idea: if p,q is a split pair with d(p,q) < s , then p and q are in Sy and at most 7 points apart


 

13. For any p=(x1, y1) and q=(x2, y2) with d(p,q) < s , draw s/2 X s/2 boxes with center x0 and bottom min{y1, y2}.

    All points in Sy with y-coordinate between p and q , lie in one of the 8 boxes. Because |y2-y1|<s , so max{y1, y2} < s , so one point is at the bottom line and the other point is within bottom line plus s that is in one of the 8 boxes.

    At most one point of Sy in each box. Because each box are either in left (Q) or in right (R) and the maxium distance of each box is s/2 * 2^1/2 < s , so if there are more than one points in the same box then the min{  d(ClosesetPair(P)) , d(ClosestPair(Q)) } should not be s.