Questions from Xin He, SUNY Buffalo, CSE 531
1. Compute Fibonacci number in O(logn) runtime.

(1)  F(n) = F(n-1) + F(n-2) ==>
     F(n)   = ( 1 1 ) F(n-1) = (1 1) (1 1)F(n-2)
     F(n-1)   ( 1 0 ) F(n-2)   (1 0) (1 0)F(n-3)
            = (1 1)...(1 1) F(1)
              (1 0)   (1 0) F(0)  
              -------------
                n times
(2) Assuming A = (1 1)
                 (1 0) 

Then how to calculate A*A*...*A (N times) in O(logN)?
Because A(N) = A(N/2) * A(N/2)
T(N) = T(N/2) + Theta(1) ==> T(N) = O(logN)


2. Describe an O(N) time algorithm to find k numbers that are closest to the
median of an array S[N].

Method One (in place):
(1) find median x in array S in O(N)
(2) partition S into S1, S2 by pivot x in O(N) such that
    [e|S1] < x, [e|S2] > x
(3) find k/2 biggest numbers in S1 in O(N)
    find k/2 smallest numbers in S2 in O(N)
Method two (extra B[N]), by Xin He:
(1) find median x in array S in O(N)
(2) In another array B[N]: B[i]=abs(S[i]-x) for i=0..N-1
(3) find k-th number y in array B in O(N)
(4) for i=0..N-1 { if (abs(S[i]-x )<= y) output S[i] }

3. Find the median of two sorted array A[N], B[N] in O(N) time

(1) find median x in A[N], separate A[N] into A1<=x<=A2
(2) find median y in B[N], separate B[N] into B1<=y<=B2
(3) if x>y then B1<=A2, that is B1 <= A2, B2
    thus the median(A,B) is the median(A1,B2):
    the median(A1,B2) z must satisfy B1<=z<=A2 
(4) if x< y then A1<=B2, that is A1 <= A2, B2
    thus the median(A,B) is the median(A2,B1)

- posted by Pop @ 12:40 PM