Week 2 Tutorial Sheet Solution

Objectives: The tutorials, in general, give practice in problem solving, in analysis of algorithms and data struc-tures, and in mathematics and logic useful in the above.

Instructions to the class: Aim to attempt these questions before the tutorial! It will probably not be possible to cover all questions unless the class has prepared them in advance. There are marks allocated towards active participation during the class. You must attempt the problems under Assessed Preparation section before your tutorial class and give your worked out solutions to your tutor at the start of the class – this is a hurdle and failing to attempt these problems before your tutorial will result in 0 mark for that class even if you actively participate in the class.

Instructions to Tutors:

    1. The purpose of the tutorials is not to solve the practical exercises!

    2. The purpose is to check answers, and to discuss particular sticking points, not to simply make answers available.

Supplementary problems: The supplementary problems provide additional practice for you to complete after your tutorial class, or as pre-exam revision. Problems that are marked as (Advanced) difficulty are beyond the difficulty that you would be expected to complete in the exam, but are nonetheless useful practice problems as they will teach you skills and concepts that you can apply to other problems.



Assessed Preparation


Problem 1.    Find a function T that satisfies the following recurrence relation:
T (n) =
¤b ,(
n  1
) +
c ,
if n = 0.

T



if n > 0,



Problem 2.    Find a function T that satisfies the following recurrence relation:
T (n) =
¤c , (
n
1
)
,
if n = 0.

3T




if n > 0,





Tutorial Problems


Problem 3.    Find a function T that satisfies the following recurrence relation:
T (n) =
¤b , (
n  1
) +
a ,
if n = 0.

2T



if n > 0,



Problem 4.    Find a function T that satisfies the following recurrence relation
T (n) =
¤1
2
+

if n = 1.

2T
n


n
if n > 1,










1

State the order of growth of the solution using big-O notation.

Problem 5.    Use mathematical induction to prove that the recurrence relation
T (n) =
¤b ,
2
+
if n = 1,

T
n


c ,  if n > 1,








has a solution given by T (n) = b + c log2(n) for all n = 2k for some k    0.

Problem 6. Let F (n) denote the nth Fibonacci number. The Fibonacci sequence is defined by the recurrence relation F (n) = F (n 1) + F (n 2), with F (1) = F (2) = 1.

(a) Use mathematical induction to prove the following property:


1
1
n
F (n + 1)
F (n)


1
0
=
F (n)
F (n  1)


(b) Prove that F (n) satisfies the following properties:



F (2k ) = F (k )[2F (k + 1)   F (k )]
(1)
F (2k + 1) = F (k + 1)2 + F (k )2

(2)
[Hint: Use part (a)]







Problem 7. Consider the following recursive function for computing the power function x p for a non-negative integer p .

    1: function POWER(x, p)

    2: if p = 0 then return 1

    3: if p is even then

    4: return POWER(x , p =2)   POWER(x , p =2)

    5: else

    6: return POWER(x , p =2)   POWER(x , p =2)   x

    7: end if

    8: end function

What is the time complexity of this function (assuming that all multiplications are done in constant time)? How could you improve this function to improve its complexity, and what would that new complexity be?

Problem 8. Write a Python function that computes F (n) (the nth Fibonacci number) by using the recurrences given in Problem 6(b). What are the time complexity and space complexity of this method of computing Fi-bonacci numbers? You may assume that all operations on integers take constant time and space.


Supplementary Problems


Problem 9.    Find a function T that satisfies the following recurrence relation:
T (n) =
¤b ,(
n
1
) +
if n = 0.

T



a n,  if n > 0,






2

Write an asymptotic upper bound on the solution in big-O notation.

Problem 10.    Find a function T that is a solution of the following recurrence relation

¤
3T    n    + n2    if n > 1,
T (n) =    2
    • if n = 1.

Write an asymptotic upper bound on the solution in big-O notation.

Problem 11. (Advanced) Consider the recurrence relation

p

T (n) = 2T (    n) + log2(n).

Although rather daunting at first sight, we can solve this recurrence by transforming it onto one that we have seen before!

    (a) Make the substitution m = log2(n) to obtain a new recurrence relation in terms of m, which should look like T (2m ) = ...

    (b) Define a new function S (m) = T (2m ), and rewrite your recurrence relation from (a) in terms of S (m)

    (c) Solve the new recurrence relation for S (m) [Hint: it is one that you have already done on this sheet!]

    (d) Use your solution from (c) to write an asymptotic bound in big-O notation for T (n)

Problem 12. (Advanced) Consider a divide-and-conquer algorithm that splits a problem of size n into a 1 sub-problems of size n=b with b > 1 and performs f (n) work to split/recombine the results of the subproblems. We can express the running time of such an algorithm by the following general recurrence.
T (n) =
¤ (1)
b
+

(

)
if n = 1.

a T
n


f

n

if n > 1












A method, often called the divide-and-conquer master theorem can be used to solve many equations of this form, for suitable functions f . The master theorem says

8
>    (nlogb (a ))
<
T (n) =    (nlogb (a ) log(n))

>
: ( f (n))

if f (n) = O (n c ) where c < logb (a ),
if f (n) =    (nlogb (a )),
if f (n) =    (n c1 ) for c1 > logb (a ) and a f    nb    c2 f (n) for c2 < 1 for large n.

In case 3, by large n, we mean for all values of n greater than some threshold nk . Intuitively, the master theorem is broken into three cases depending on whether the splitting/recombining cost f (n) is smaller, equal to, or bigger than the cost of the recursion.

    (a) Verify your solutions to the previous exercises using the master theorem, or explain why the master theo-rem (as stated above) is not applicable

    (b) Use telescoping to show that a solution to the master theorem satisfies the following

logb (n)  1
n

X



T (n) =  (nlogb (a )) +
a i f

.


b i

i =0








    (c) Using Part (b), prove the master theorem. You may assume for simplicity that n is an exact power of b , ie. n = b i for some integer i , so that the subproblem sizes are always integers. To make it easier, you should prove each of the three cases separately.





3