Question 1 [12 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.
Yes it is stable, but care needs to be put into ensuring that comparisons are strict inequalities.
Yes it is stable, because it is like bubble sort, comparing adjacent elements only, thus it is stable.
3 marks for correct, 1 mark for unsatisfactory explanation.
(2) Is it possible for O(N) code to run faster than O(1) code, explain your answer.
Yes, it is possible. For example, for small N. f(N) = O(g(N)) implies f(N) is bounded by c ∗ g(N) only above some arbitrary (but finite) N threshold. Below this threshold, anything goes.
3 marks for this or some other well-argued reason. 1 mark if explanation not completely satisfactory.
(3) How do best and worst case differ for merge-sort and why?
They don’t. Best and worst case merge-sort are O(Nlog(N)). Each recursive call splits the list in half regardless of list content.
3 marks. 1 mark if explanation not completely satisfactory.
(4) What is the worst-case time complexity of quicksort and when does it happen? O(N2), when the pivot is happens to be reduce the size of the list by 1 in each
partition.
3 marks. 1 mark if explanation not completely satisfactory.
Page 2 of 7
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. def sum_of_digits_tr(x):
return sum_of_digits_tr_aux(x, 0)
def sum_of_digits_tr_aux(x, result): if x < 10:
return x + result else:
return sum_of_digits_tr_aux(x//10, result + x%10)
– 3 marks for correctly setting up first call
– 3 marks for a solution that is tail-recursive
– 3 marks for handling base case correctly
– 4 marks for correct handling of recursive case
• Whatarethebestandworst-casetimecomplexityofthenon-tailrecursivesum_of_digits. Explain your answer – no explanation means no marks.
Best and worst case are the same. The operations in each recursion are O(1), thus the complexity equals the recursive depth. The input x loses a digit each recur- sion, so the time complexity is linear in the number of digits in x, which implies O(log(x))
– 3 marks for identifying best = worst.
– 3 marks for identifying meaningful input is number of digits
– 4 marks for correct explanation, O(d) where d is number of digits also valid.
Page 3 of 7
2
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
0x7FFEFDC
0x7FFEFE0
0x7FFEFE4
0x7FFEFE8
0x7FFEFEC
0x7FFEFF0
0x7FFEFF4
0x7FFEFF8
0x7FFEFFC
0x7FFF000
3
6
2
4
0
3
0
0x7FFFB3114
0x00400000
2
0x10014F20
count n
i saved $fp saved $ra k
a_list
Registers
$fp $sp
0x7FFEFF0
0x7FFEFE4
Page 4 of 7
• 7 marks for local variables as follows:
– 2 marks correct value of variable i
– 2 marks correct value of variable n
– 2 marks correct value of variable count
– 1 mark for correct names in all local variables
• 3 marks for correct values in registers fp and sp (1.5 each)
• 10 marks for correctly saved arguments as follows:
– 1 mark for list argument name
– 1 mark for k argument name
– 4 marks for list argument content on stack – 4 marks for k argument content on stack
• 10 marks for correctly saved fp and sp as follows:
– ra value correct address 4 marks – fp value correct address 4 marks – ra correct name 1 mark
– fp correct name 1 mark
• 5 marks for heap content including list size (ignore globals in heap if they are put in there)
Page 5 of 7
3
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
.data
n: .word 19 base: .word 0 .text
# read int
addi $v0, $0, 5 syscall
sw $v0 ,
#if n <= loop:
lw $t0, n ble $t0 , $0 ,
# t0 = n (t1) lw $t1, n
lw $t2, base div $t1 , $t2 mfhi $t0
endloop
% base (t2)
#print n%base addi $v0, $0, addi $a0, $t0, 0 syscall
# n = n lw $t1, lw $t2, div $t1 , mflo $t0 sw $t0, j loop endloop: li $v0 , syscall
1
// base n
base
$t2 n
10
base
0, go to endloop
• 2 marks for useful comments
• 2 marks for correct global variables
• 5 marks for correct sycalls
• 7 marks for business logic inside the loop • 4 marks for faithfulness
Page 6 of 7
• 10 marks for correct looping as follows:
– 5 marks for correct condition
– 1 mark for looping back to condition
– 1 mark for correctly ending loop
– 3 marks for correctly updating counter
Page 7 of 7
3