1. Algorithms for the Fibonacci Function

To prove:

$\begin{displaymath}\left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]^n ... ...n{array}{cc} f(n+1) & f(n) \\ f(n) & f(n-1) \end{array}\right]\end{displaymath}$

Induction. Base case: n = 2. By simple matrix multiplication, $\left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]^2 = \left[\begin{arr... ...right] = \left[\begin{array}{cc} f(3) & f(2) \\ f(2) & f(1) \end{array}\right]$ , so the base case holds.

Induction hypothesis: Suppose the claim holds for n = k. In other words, $\left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]^k = \left[\begin{array}{cc} f(k+1) & f(k) \\ f(k) & f(k-1) \end{array}\right]$ .

Induction step: Prove that the claim holds for n = k+1:

$\begin{array}{rcll} \left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]^... ... f(k+1) & f(k) \end{array}\right] & \mbox{(definition of $f(n)$ )} \end{array}$

So the induction step holds, and the result follows for all n>1 by induction.

2. Binary Search

Strong induction on n.

Base case: n = 1. $T(1) = 1 = 1 + \lfloor \log 1 \rfloor$ . Base case holds.

Induction hypothesis: Suppose the claim holds for all n < k.

Induction step: Prove that the claim holds for n = k. Two cases: k is even, or k is odd.

Case 1: k = 2j for some integer j.

$\begin{array}{rcll} T(k) & = & 1 + T(\lfloor \frac{k}{2} \rfloor) & \mbox{(defi... ...loor \log(2j) \rfloor & \\ & = & 1 + \lfloor \log k \rfloor & \\ \end{array}$

Case 2: k = 2j+1 for some integer j. Note that $j \geq 1$ , since, aside from the base case, $k \geq 2$ . Note also that, $\forall j \geq 1$ , $\log(2j) = \log(2j+1)$ , since the $\log$ only changes in increasing from an odd to an even (eg, $\log 15 \neq \log 16$ ), never from an even to an odd.

$\begin{array}{rcll} T(k) & = & 1 + T(\lfloor \frac{k}{2} \rfloor) & \mbox{(defi... ...og(2j) = \log(2j+1)$ )} \\ & = & 1 + \lfloor \log k \rfloor & \\ \end{array}$

So in both cases the induction step holds, and the result follows for all $n \geq 1$ by induction.

3. The Skyline Problem in Computer Graphics

Merging two skylines is doable in linear time. Here is the sketch of the algorithm:

(a) initializing step: Advance to the first line causing an intersection of the two skylines.
(b) Detect which of the 2 skylines has the lowest y value at this x-position.
(c) Draw this skyline until the next intersection.
(d) go back to 2 until the end of a skyline has been reached.

Now, practically how do we do this in linear time?
Let's assume a skyline is given by two arrays storing the x and y values, we then have:

Sky1x, Sky1y both of size n
Sky2x, Sky2y both of size m

Our goal is to build Sky3x, Sky3y 2 arrays of size n+m representing the intersection of the 2 skylines.
In other words Sky3x is the merged sorted list of Sky1x and Sky2x
and Sky3y contains the lowest value of Sky1y and Sky2y when the skylines are overlapping and 0 when they are not.

Here is the initialization:

i = 0;
j = 0;
k = 0;
// Advance to the first intersection point
// and sets the height of all points previous 
// to the intersection to 0
while (Sky1x[i] < Sky2x[0])
 Sky3x[i] = Sky1x[i];
 Sky3y[k] = 0;
 i = i + 1;
 k = k + 1;
end
while (Sky2x[j] < Sky1x[0])
 Sky3x[i] = Sky1x[i];
 Sky3y[i] = 0;
 j = j + 1;
 k = k + 1;
end

Now the main loop

while (i<n) and (j<n)
  // Check which x value to insert 
  if (Sky1x[i]<Sky2x[j])
    // Insert the x value
    Sky3x[k] = Sky1x[i];
    // Select the lowest height and insert it
    Sky3y[k] = min(Sky1y[i],Sky2y[j-1])
    i = i + 1;
  else
    Sky3x[k] = Sky2x[i];
    Sky3y[k] = min(Sky1y[i-1],Sky2y[j])
    j = j + 1;
  k = k + 1;
end

Clearly this algorithm is linear as it scans only once each input array.

4. Analysis of Heap Sorting

(a) Check Luc Devroye's class notes on heaps

(b) To prove: $\sum_{i=1}^{n} log(i) = \Omega(n log(n))$ $\begin{array}{rcll} \sum_{i=1}^{n} log(i) & = & log(n)+log(n-1)+...+log(n/2)+..... ...es)}\\ & \geq & (n/2) log(n/2) & \\ & = & \Omega(n log(n))& \\ \end{array}$

Sylvain Bouix
2000-10-19