Homework Assignment 2

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 containing exactly one node is 0, the height of the tree tree 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.

    1. Prove that ∀h ∈ N, s(h+1) > s(h).

    2. 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).

    3. Use your recurrence to prove that ∀h ∈ N, s(h) ≥ φh, where φ = (1 + √5) / 2. (The number φ has the property that φ2 = φ + 1 — you may use this in your solution.)

    4. 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 a2) — 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, F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 ∀n ≥ 2. 

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

        # Precond:  n ∈ N
    # Postcond:  returns [Fn-1, Fn]
    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 [Fn-1, Fn]
    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, F2n-1 = (Fn-1)2 + (Fn)2,
    • ∀n ≥ 1, F2n = 2 (Fn-1) (Fn) + (Fn)2.

    BONUS!

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

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

    2. Suppose that each algorithm is run on a machine that can execute 109 operations per second. For each algorithm, compute the largest value of n for which Fn 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) ∈ Θ(n2), then T(n) = n2 exactly). Show your work.