There are five problems listed below.  To get full credit for this assignment you need to complete all of them!

If you are stuck or confused by any of the problems, feel free to post on Piazza!

Show all working; if you do not show your work the mark will be reduced. You should submit via Canvas a single PDF file containing the answers to the written questions. A scanned handwritten submission is acceptable if and only if it is very neatly written (if it’s hard to read, it will not be marked). If typing the assignment, do the best you can with mathematical symbols. For exponents, write something like

2^n

if using plain text. Use LaTeX if you really want it to look good.

Answers to programming questions must be submitted via the automated marker system: https://www.automarker.cs.auckland.ac.nz/student.php.

Please try to submit your assignments no later than 5 min before the due time.  Even though the time is a universal thing your watch and Canvas built-in clock could show the different time.  It is quite possible that you might be on time on your watch and late on Canvas.  To avoid these kind of situation submit the assignments at least 5 min before the due time.

Please note that late assignments cannot be marked under any circumstances.  (With that said: if you find yourself unable to complete this assignment due to illness, injury, or personal/familial misfortune, please email us as soon as possible. We can come up with solutions to help you succeed in CS220!)

Best of luck, and enjoy the problems!

1.  (10 marks) Suppose you are given 3 algorithms A1,A2  and A3  solving the same problem. You know that in the the running times are

T1(n) = n5n ,        T2 (n) = 210n2 + n3 ,        T3 (n) = 105 log10 (nn )

(a) Which algorithm is the fastest for very large inputs? Which algorithm is the slowest for

very large inputs? (Justify your answer.)

(b) For which problem sizes is A2  the better than A1? (Justify your answer.)

(c) For which problem sizes is A2  the better than A3? (Justify your answer.)

2.  (10 marks) Asymptotic Notations:

(a) Prove using definitions only that nn log(n) is not O(nn ). (HINT: proof by contradiction)

(b) Prove that n3 − 50 is Ω(n2 ), either with limit laws or definitions.

(d) Suppose that f,h,g,k are functions and that f = h · g + k .  Suppose further, that h is O(n2 ), g is Θ(log(n)) and k is Ω(n).  What do we know about f?  State everything we can determine for full marks.

3.  (10 marks) Elementary operations and algorithms:

(a) Work out the number of elementary operations in the following algorithm.   For this

exercise only count the constant number C of elementary operations as executed on lines 2 and 4.

0: function Blah (positive integer n)

1:    for i ← 2 to n do

2:            Constant number C of elementary operations.

3:          for j ← 1 to i do

4:                  Constant number C of elementary operations.

(b) Work out the number of elementary operations the following algorithm uses in an average case. You can assume that the probability of getting a number divisible by 3 is  .

0: function Meh (positive integer n)

1:    if n%3 = 0 do

2:            for i ← 0 to n − 1 do

3:                    for j ← 0 to n − 1, j ← j + 2 do

4:                           if i = j do

5:                              for k ← 0 to n4 , k ← k + n2  do

6:                                      Constant number C of elementary operations. 7:                       else

8:                               Constant number C of elementary operations.

9:    else

10:            Execute Meh(3n2 )

4.  (10 marks) Elementary operations and algorithms:

(a) What is the explicit form of the following recurrence relation:

T(n) = 3T(n/3) + 1;    T(1) = 1.

(b) What is the explicit form of the following recurrence relation:

T(n) = T(n − 1) + log2 n;    T(0) = 0. Hint n! is approximately ^2πnnn e −n .