===========================================================================
CSC 236           Homework Exercise 4 -- Sample Solutions       Winter 2008
===========================================================================


1.  Recurrence (from Exercise 3):
        T(0) = 3,
        T(y) = 11 + T(|_y/2_|)  \-/ y > 0.

    The Master Theorem applies with a_1 = 0, a_2 = 1, b = 2, and
    f(y) (- \Theta(y^0).  Hence, a = a_1 + a_2 = 1 = 2^0 = b^d and
    T(y) (- \Theta(y^d log y) = \Theta(y^0 log y) = \Theta(log y).


2.  (a) Recurrence:
            T(0) = 3  (if == return);
            T(y) = 5 + T(y-1)  \-/ y > 0  (if == return * -).

        The Master Theorem does NOT apply because the general term of the
        recurrence does not have the form
                a_1 T(|^n/b^|) + a_2 T(|_n/b_|) + \Theta(n^d)
        for constants a_1 >= 0, a_2 >= 0, b > 1, d >= 0.

        However, repeated substitution yields
            T(y) = 5 + T(y-1)
                 = 5 + 5 + T(y-2)
                 = ...
                 = 5(y) + T(0)
                 = 5 y + 3
        which can be proved by simple induction:
         -  T(0) = 3 = 5(0) + 3,
         -  T(y) = 5 + T(y-1) = 5 + 5(y-1) + 3 = 5 y + 3,
            supposing y > 0 and T(y-1) = 5(y-1) + 3.

        Hence, \-/ y (- N, T(y) = 5 y + 3.

    (b) Precondition:  x (- R, y (- N.
        Postcondition:  Q(x, y) returns x^y.

    (c) Proof that \-/ x (- R, Q(x, y) returns x^y, by simple induction on
        y (- N:

        1.  Base Case (y = 0):  Suppose x (- R.  Then Q(x, 0) returns 1 =
            x^0, by the first two lines of the algorithm.

        2.  Ind. Hyp.:  Suppose y >= 0 and \-/ x (- R, Q(x, y) returns x^y.

        3.  Ind. Step:  Suppose x (- R and consider the call Q(x, y+1).
            Since y+1 >= 1, the algorithm executes lines 3-4.  By the IH,
            Q(x, y) returns x^y, so Q(x, y+1) returns x * x^y = x^{y+1}.

        4.  By induction, \-/ y (- N, \-/ x (- R, Q(x, y) returns x^y.