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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注