===========================================================================
CSC 236                     Homework Exercise 4                 Winter 2008
===========================================================================

Due:  by 10am on Thu 28 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.  Recall the following algorithm (from Exercise 3).

            # Precond:  x (- R, y (- N.
            # Postcond:  returns x^y.
            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

    Find a tight bound on the worst-case running time of the algorithm --
    apply the Master Theorem if appropriate (in which case please explain
    how you are applying it, i.e., clearly state the values of all the
    constants involved and which case of the Theorem applies).


2.  Consider the following algorithm.

            Q(x, y):
                if y == 0:
                    return 1
                else:
                    return x * Q(x, y-1)

    (a) Find a tight bound on the worst-case running time of the algorithm
        -- apply the Master Theorem if appropriate (in which case please
        explain how you are applying it, i.e., clearly state the values of
        all the constants involved and which case of the Theorem applies).
        Hint:  Remember that an exact value is even better than a
        \Theta-expression.

    (b) Give clear and precise preconditions and postconditions for the
        algorithm -- make your preconditions as weak as possible and your
        postconditions as strong as possible.

    (c) Give a detailed proof of correctness for the algorithm, following
        the format given in class.