Entrepreneurials‎ > ‎Jobs‎ > ‎Interview‎ > ‎Examples‎ > ‎

Divide and Conquer

Maximum Sub-array

Problem: You have an array of prices of a single product. Yo can buy only once and sell only once and calculate profit at the end. You know all the daily prices.
Solution: Instead of looking at daily prices look at daily change in price

Find-Maximum-Subarray(A, low, high)
 If high == low
    return ( low, high, A[low] )
 else
   mid = floor( (low + high)/2 )
 
  (left-low, left-high, left-sum) = Find-Maximum-Subarray(A, low, mid)
   (right-low, right-high, right-sum) = Find-Maximum-Subarray(A, mid+1,high)
   (cross-low, cross-high, cross-sum) = Find-Max-Crossing-Subarray(A,low,mid,high)
 
   if left-sum >= right-sum and left-sum >= cross-sum
         return (left-low, left-high, left-sum)
   elseif right-sum >= left-sum and right-sum >= cross-sum
         return (right-low,right-high,right-sum)
   else
         return(cross-low,cross-high,cross-sum)
//------------------------------------------------------------------
Find-Max-Crossing-Subarray(A, low, mid, high)
left-sum = -inf
sum=0
for i = mid downto low
sum=sum +A[i]
if sum > left-sum
left-sum = sum
max-left= i
right-sum = -inf
sum=0
for j = mid +1 to high
sum = sum + A[j]
if sum > right-sum
right-sum = sum
max-right = j
return (max-left; max-right; left-sum + right-sum)
//========================
T(n) = Θ(1),     if n = 1    
T(n) = 2T(n/2) + Θ(n),      if n > 1
//========================
T(n) = Θ(n lg n)

Matrix Multiply

Square Matrix Multiply

SQUARE-MATRIX-MULTIPLY(A,B)
1 n = A.rows
2 let C be a new n x n matrix
3 for i = 1 to n
4    for j = 1 to n
5        c_ij = 0
6        for k = 1 to n
7            c_ij = c_ij  +  a_ik x b_kj
8 return C

Square Matrix Multiply Recursive (Divide and Conquer)

Assume: n is a power of 2

subdivide A, B, and C into four n/2 x n/2 submatrices:
A = | A_11 A_12 |  B = | B_11 B_12 |   C = | C_11 C_12 |
       | A_21 A_22 |        | B_21 B_22 |         | C_21 C_22 |

then looking at the 4 submatrices of C = A * B
C_11 = A_11 * B_11  +  A_12 * B_21
C_12 = A_11 * B_12  +  A_22 * B_22
C_21 = A_21 * B_11  +  A_12 * B_21
C_22 = A_21 * B_12  +  A_22 * B_22

MATRIX-MULTIPLY-RECURSE(A,B)
1 n = A.rows
2 let C be a new n x n matrix
3 if n == 1
4   c_11 = a_11 * b_11
5 else partition A, B, and C as 4 submatrices
6   C_11 = MATRIX-MULTIPLY-RECURSE(A_11,B_11) + MATRIX-MULTIPLY-RECURSE(A_12,B_21)
7   C_12 = MATRIX-MULTIPLY-RECURSE(A_11,B_12) + MATRIX-MULTIPLY-RECURSE(A_12,B_22)
8   C_21 = MATRIX-MULTIPLY-RECURSE(A_21,B_11) + MATRIX-MULTIPLY-RECURSE(A_22,B_21)
9   C_22 = MATRIX-MULTIPLY-RECURSE(A_21,B_12) + MATRIX-MULTIPLY-RECURSE(A_22,B_22)
10 return C

//==================================
there are 8 recursive calls to problems of size n/2, for 8T(n/2) time. There are also 4 matrix additions of (n/2)^2 entries for Theta(n^2) time.  Thus:

T(n) = Θ(1) + 8T(n/2) + Θ(n^2)
        = 8T(n/2) + Θ(n^2)
        = Θ(n^3)

Strassen's Method

Consider multiplying two 2x2 matrices, as follows:
|A B| * |E F| = |AE+BG   AF+BH|
|C D|   |G H|   |CE+DG   CF+DH|
The obvious way to compute the right side is just to do the 8 multiplies and 4 additions. But imagine multiplies are a lot more expensive than additions, so we want to reduce the number of multiplications if at all possible. Strassen uses a trick to compute the right hand side with one less multiply and a lot more additions (and some subtractions).
Here are the 7 multiplies:
M1 = (A + D) * (E + H) = AE + AH + DE + DH
M2 = (A + B) * H = AH + BH
M3 = (C + D) * E = CE + DE
M4 = A * (F - H) = AF - AH
M5 = D * (G - E) = DG - DE
M6 = (C - A) * (E + F) = CE + CF - AE - AF
M7 = (B - D) * (G + H) = BG + BH - DG - DH
So to compute AE+BG, start with M1+M7 (which gets us the AE and BG terms), then add/subtract some of the other Ms until AE+BG is all we are left with. Miraculously, the M's are chosen so that M1+M7-M2+M5 works. Same with the other 3 results required.


















Comments