Homework Exercise 4

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

    1. 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 Θ-expression.

    2. Give clear and precise preconditions and postconditions for the algorithm — make your preconditions as weak as possible and your postconditions as strong as possible.

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