===========================================================================
CSC 236                     Homework Exercise 3                 Winter 2008
===========================================================================

Due:  by 10am on Thu 14 Feb
Worth:  1.5%

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.  Give a recurrence relation for the worst-case running time of the
    following algorithm.  Remember to define n precisely (as a function of
    x and/or y) and to justify that your recurrence is correct (based on
    the algorithm).

        # Precondition: x,y (- N
        P(x, y):
            if y == 0:
                return 1
            elif y % 2 == 0:   # y is even
                t = P(x, y/2)
                return t * t
            else:
                t = P(x, (y-1)/2)
                return t * t * x


2.  Perform repeated substitution for the following recurrence, to obtain
    an approximate closed-form.  Show all of your work and simplify your
    final answer as much as possible.

        T(0) = 1,
        T(n) = 2 T(floor(n/4)) + n - 1   \-/ n >= 1.

    You may find the following facts useful:

     -  For all real numbers r and all natural numbers k,
        1 + r + r^2 + ... + r^k = (1 - r^{k+1}) / (1 - r).

     -  a^{log_b c} = c^{log_b a} for all positive real numbers a, b, c.