Q1)

(a)  Consider  the  following  six  functions.  Choose  only  one  of  the  following asymptotic running times for each function and write a, b, c, or d in your answer sheet.

[5 marks]

(b) Arrange the functions (fi ) in ascending order of running time and write your answer on the answer sheet.

[5 marks]

Q2)

Consider the following two functions:

f1 (n) = a log10  (n)

f2 (n) = b nc

Where a , b are non-zero positive constants, and c > 0 is a real value. A student is comparing the relative asymptotic running time of these two functions. They can see that if c = 1 (i.e., f2  is a linear function) that the long-term growth rate of f2  is greater than f1 .

(a) If a = 20, b = 3.0 and c = 0.5, for what value of n would the long-term growth rate of f2  permanently exceed that of f1 ? Fill in the blank on the answer sheet.

[5 marks]

(b) For values of c > 0, but < 1, explain whether you think it is possible for the long-term growth rate of f1 to exceed that of f2 . Fill in the blanks and check the correct box on the answer sheet.

[5 marks]

Q3)

Specify the running time of each of the following algorithms. You should clearly state the performance in the best and worst cases, and you should consider in each case the upper and lower bounds and whether a tight bound exists. Fill in the

blanks and write your answers on the answer sheet.

(a)

Specify the running time where n, m go to infinity. Note: If i > m , you should assume that

the for loop does not run (does not iterate backwards).                              [6 marks]

(d) A data pattern analyser is to be built that can analyse a sequence and detect and count up the number of occurrences of three consecutive integers where the third integer is the sum of the first and second integers. Integers can be positive or negative. The analyser needs to stop counting and terminate immediately if it

reaches an element in the sequence with value 0.

So:

•   Sequence (1, -1, 0) would return 0 (termination condition)

•   Sequence (1, 2, 3) would return 1

•   Sequence (1, 1, 3, 4) would return 1

•   Sequence (1, 2, 3, 5) would return 2 (the sequences (1, 2, 3) and (2, 3, 5))

•   Sequence (1, 2, 3, 0, 1, 4, 5, 1) would return 1 (because it stops counting and terminates immediately after reaching the element with value 0).

In your answer sheet, write a linear algorithm to solve the problem using a pseudo- code style similar to the one shown in parts (a) to (c), and state the running time of your algorithm. Note: As the question asks for a linear algorithm, try to use a single loop only. You are not allowed to use any nested loops which might make the worst case non-linear.

[10 marks]

(e) Two programs A and B are developed that solve the same problem. A student conducts an experiment to see how the running time of each program varies with the size of the input problem set. A summary of the data they collect is shown below. We are told that the data the two programs are tested with represents a worst-case scenario of the problem.

Based on the data available, what conclusions may we draw about the running time  complexity  classes  of the algorithms that the two  programs  implement? Please fill in the blanks on the answer sheet.

[8 marks]

Q4)

You are helping to design an encryption algorithm. The decryption phase of the algorithm takes two inputs, a message of length a digits and a key made up of n binary  bits.  The  decryption  phase  performs  a  mathematical  process  on  the message using the key to produce the plain text decoded message. You are very aware that there are hackers that would wish to be able to decode your messages. However, the workings of the algorithm have been kept secret so the only hack available for decoding the message is a brute force approach where each possible key is tried one at a time until the correct one is found, when a decoded message in English is produced. There are no known cribs, weaknesses, or other techniques to assist in hacking the cipher.

(a) What is the running time for a brute force method to decode a message? Fill in the blanks on the answer sheet.

[5 marks]

(b) Should the lower bound you identified in part (a) concern us in terms of the safety and security of our encryption technique? Fill in the blanks and check the correct boxes on the answer sheet.

[5 marks]

(c) The security of the encryption process depends on the value n . The decryption process is quite complex. Assume it takes 20 seconds of processing time on a PC to apply a key (regardless of n and a values) to the message (regardless of whether it’s the correct key). The algorithm may be regarded as sufficiently secure provided that, using a brute force method, there is no more than a 1% chance that the message would be decoded correctly in 30 days (working 24 hours a day). Fill in the blanks on the answer sheet and calculate the minimum number of bits n that the key must be composed of.

[10 marks]

(d) In reality, the time it takes to apply the key depends on the lengths of n and a . If the key is short, the application time is quick. If the key is long, it takes longer to apply. We discover that the time to apply the key to the message is given by the formula t  =  0.02a × n2  where n is the number of bits in the key, a is the length of the message and t is the time in seconds. This time the algorithm may be regarded as sufficiently secure provided that, using a brute force method, there is no more than a 0.1% chance that the message of 200 characters would be decoded correctly in 30 days (working 24 hours a day). Fill in the blanks on the answer sheet and determine the minimum number of bits n that the key must be composed of.

[10 marks]

Q5)

This question concerns Dijkstra’s algorithm which is reproduced overleaf:

You will be considering what happens when the algorithm is run on the following graph where the source vertex is v1 . Note that this graph contains a negatively weighted edge.