1. In each of the following situations, indicate whether f = O(g) or f = Ω(g) or f = Θ(g) by writing “true” in the respective cells.

(1 marks)

2. An algorithm with running time Θ(,n(log n)2 ) spends exactly 1 millisecond to process an input of 1,024 data items. Assuming that the time T (n) of processing n items is directly proportional to,n(lg n)2 , that is T (n) = c,n(lg n)2  (“lg” denotes “base-2 log”), derive a formula for T (n), and estimate how long this algorithm will process 216  items.

(1 marks)

3.  Suppose you are given two algorithms A, B that solve the same problem. The running time of A is TA (n) = cn2  and the running time of B is TB (n) = dn lg n where c, d are constants (and “lg” denotes “base-2 log”). Suppose that for small values of n, A runs faster than B . Moreover, when n = 210 , these two algorithms have the same running time.  What is the value of n for which the running time of A is exactly 512 times the running time of B?

(1 marks)

4.  Suppose you are given 3 algorithms A1 , A2  and A3  solving the same problem. You know that the running times of the three algorithms are respectively:

● T1 (n) = (2100 log n + n)(n2 + 100n log n),

● T2 (n) = 1.01n (n _ 3)1.5 ,

● T3 (n) = 1012n log10 2n + (10 log n)10 .

Which algorithm is the fastest for very large inputs?  Which algorithm is the slowest for very large inputs?

(1 marks)

5. Work out the number of elementary operations for the following algorithm. Analyse the asymp- totic behaviour of the running time growth function with respect to the input n (a positive integer).

function soMEALco(n)

a - 0

b - 1

for i = 1; i < n; i - i + 1 do

c - 0

for j = 1;j < a + b;j - j + 1 do

c - c + 1

end for

a - b

b - c

end for

return b

end function

(1 marks)

6. Derive an explicit (closed-form) formula for time T (n) of processing an array of size n if T (n) is specified implicitly by the recurrence:

T (n) = (T (0) + T (1) + . . . + T (n _ 1)) + cn;

T (0) = 0.

(1 marks)

7. The following algorithm takes as input two length-n positive integers a, b. Analyse the asymp- totic behaviour of this algorithm, treating all assignment operation, comparisons, control flow,

and arithmetic operations as elementary. Note that   mod  refers to the modulo operation, i.e.,

a mod b outputs the remainder of a ÷ b.

Express the best-case and the worst-case running time of the algorithm using Θ-notation, with respect to the input length n.

function ALco(a, b)

Require: Integers a, b

if a < b then

c - b

b - a

a - c

end if

while b  0 do

c - a mod b

a - b

b - c

end while

return a

end function

(2 marks)

8. Programming question:

● Question: Write a program that takes input a sequence of names with two attributes, and prints out the list of names whose first attributes are 0 and second attributes are sorted (in ascending order).  This question has two purposes:  (1) for you to obtain familiarity with the automated marker system which will be used more in later assignments; and (2) for you to get familiar with sorting algorithms.

● Algorithm:  To practice your algorithm abilities, please refrain from calling the system sort function. In this way, you should implement the sorting algorithm yourself. We will monitor your code and those who call the system sort function may not receive their mark.

● Input: The input consists of a number of lines. Each line contains a name, a 0/1-valued attribute, and another attribute whose value is a positive integer.  The names and the attributes are separated by space ‘  ’ . For example:

William  1  21

Mary  0  25

John  1  19

Lingling  0  21

Rachel  0  14

Adam  1  17

Vivian  0  21