Homework Exercise 3

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(⌊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 + r2+ ... + rk = (1 - rk+1) / (1 - r).
    • alogbc = clogba for all positive real numbers a, b, c.