This page intentionally left blank, use if needed but it will not be marked.
Page 2 of 9
Question 1 [12 = 3 x 4 marks]
In this part you are required to answer the following short questions. Your answer should be concise. As a guideline, it should require no more space than the space that is provided.
(1) Is shaker sort stable? Explain your answer.
(2) Is it possible for O(N) code to run faster than O(1) code, explain your answer.
(3) How do best and worst case differ for merge-sort and why?
(4) What is the worst-case time complexity of quicksort and when does it happen?
Page 3 of 9
12
This page intentionally left blank, use if needed but it will not be marked.
Page 4 of 9
Question 2 [23 = 13 + 10 marks]
The following function returns the sum of the digits composing a number x. For example, sum_of_digits(35) will return 8.
def sum_of_digits(x): if x < 10:
return x else:
return (x % 10) + sum_of_digits(x//10)
• Provide a tail-recursive version of the sum_of_digits algorithm.
• Whatarethebestandworst-casetimecomplexityofthenon-tailrecursivesum_of_digits. Explain your answer – no explanation means no marks.
Page 5 of 9
23
This page intentionally left blank, use if needed but it will not be marked.
Page 6 of 9
Question 3 [35 marks]
Consider the following python code, which you wish to translate into MIPS.
a=2 result = 0
l = def
[6, 2, 4]
my_function(k, a_list): i=0
n = len(a_list)
count = 0
#HERE
while i < n:
if a_list[i] % k == 0: count +=1
i+=1 return count
result = my_function(a, l) print(result)
Complete the MIPS memory diagram below when code execution reaches the line marked with the comment HERE. Include names and contents. Memory addresses are provided. Before reaching my_function, ra = 0x00400000 and fp = 0x7FFFB3114.
Heap
Stack
Name
Content
Address
0x10014F20
0x10014F24
0x10014F28
0x10014F2C
0x10014F30
0x10014F34
0x7FFEFDC
0x7FFEFE0
0x7FFEFE4
0x7FFEFE8
0x7FFEFEC
0x7FFEFF0
0x7FFEFF4
0x7FFEFF8
0x7FFEFFC
0x7FFF000
Registers
$fp $sp
Page 7 of 9
35
This page intentionally left blank, use if needed but it will not be marked.
Page 8 of 9
Question 4 [30 marks]
This question is about MIPS programming. Translate the following Python code faith- fully into MIPS assembly language. Note that in this piece of code all variables are global variables. Add comments to your MIPS code to facilitate readability. Use only instructions or pseudo-instructions in the MIPS reference sheet.
n = 19
base = int(input()) while n > 0:
print(n % base) n = n // base
Page 9 of 9
30