===========================================================================
CSC 236                    Homework Assignment 2                Winter 2008
===========================================================================

Due:  by 10am on Thu 6 Mar
Worth:  8%

For each question, please write your answer carefully.  Keep in mind that
approximately half of the marks for each question will be given purely for
having the correct proof structure, written up clearly and precisely,
irrespective of the correctness of the proof.  Also, make sure that you use
notation and terminology correctly, and that you explain and justify what
you are doing -- marks *will* be deducted for incorrect or ambiguous use of
notation and terminology, and for making incorrect, unjustified, ambiguous,
or vague claims in your solutions.


1.  Consider the following recurrence relation.

        T(n) = n   if 0 <= n <= 1,
        T(n) = 2 T(|_n/4_|) + 3 T(|^n/6^|) + 5 n   if n > 1.

    Find and prove good upper and lower bounds for T(n).

    Hint: Use the fact that |^n/6^| <= |_n/4_| for all n >= 8, and multiply
    your upper bound by 2 before you attempt to prove it...


2.  In this question, we use recurrence relations to analyze a quantity
    other than the running time of a recursive algorithm.

    The "height" of a binary tree is the number of _edges_ on a longest
    path from the root down to a leaf.  For example, the height of the tree
                                                              O
                                                             / \
                                                            O   O
                                                             \
    containing exactly one node is 0, the height of the tree  O  is 2, and
    by convention, the height of the empty tree (with no nodes) is defined
    to be -1.
    A binary tree is "height-balanced" if, for every node x in the tree,
    the height of the left subtree of x differs from the height of the
    right subtree of x by at most one, i.e., both subtrees have the same
    height, plus or minus 1.

    For all h (- N, define s(h) to be the smallest number of nodes in all
    height-balanced binary trees with height h.

    (a) Prove that \-/ h (- N, s(h+1) > s(h).

    (b) Give a recurrence relation for s(h).  Make sure to include
        appropriate base case(s) and to justify the correctness of your
        recurrence (i.e., explain briefly how you obtained your
        recurrence).

    (c) Use your recurrence to prove that \-/ h (- N, s(h) >= \phi^h, where
        \phi = (1 + \sqrt{5}) / 2.  (The number \phi has the property that
        \phi^2 = \phi + 1 -- you may use this in your solution.)

    (d) Use what you know about s(h) from the previous parts to derive an
        upper bound on the maximum height of all *height-balanced* binary
        trees with n nodes.


3.  Consider the three algorithms below to compute Fibonacci numbers, where
    "**" is used as an exponentiation operator (so "a**2" computes a^2) --
    recall that the Fibonacci sequence is defined as follows (including an
    extra special case for -1, which will turn out to be useful):
    F_{-1} = 1, F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} \-/ n >= 2.

        # Precond:  n (- N
        # Postcond:  returns F_n
        Fib1(n):
            if n == 0 or n == 1:
                return n
            else:
                return Fib1(n-1) + Fib1(n-2)

        # Precond:  n (- N
        # Postcond:  returns [F_{n-1}, F_n]
        Fib2(n):
            if n == 0 or n == 1:
                return [1-n, n]
            else:
                F = Fib2(n-1)
                return [F[1], F[0] + F[1]]

        # Precond:  n (- N
        # Postcond:  returns [F_{n-1}, F_n]
        Fib3(n):
            if n == 0 or n == 1:
                return [1-n, n]
            elif n % 2 == 0:   # n is even
                F = Fib3(n/2)
                return [F[0]**2 + F[1]**2, 2*F[0]*F[1] + F[1]**2]
            else:
                F = Fib3((n-1)/2)
                return [2*F[0]*F[1] + F[1]**2, F[1]**2 + (F[0]+F[1])**2]

    Prove the correctness of Fib1, Fib2, and Fib3, following the format
    given in class.  In your solution, you may make use of the following
    facts about Fibonacci numbers (without proving them):
     -  \-/ n >= 1, F_{2n-1} = (F_{n-1})^2 + (F_n)^2,
     -  \-/ n >= 1, F_{2n} = 2 (F_{n-1}) (F_n) + (F_n)^2.

    BONUS!

    Let T_i(n) represent the worst-case running time of Fibi(n), for
    i = 1,2,3.

    (a) Find and prove a tight bound on T_i(n), for i = 1,2,3.

    (b) Suppose that each algorithm is run on a machine that can execute
        10^9 operations per second.  For each algorithm, compute the
        largest value of n for which F_n can be computed within one full
        day.  For this computation, assume that all your bounds have a
        constant factor of 1 (e.g., if T(n) (- \Theta(n^2), then T(n) = n^2
        exactly).  Show your work.