程序代写代做 algorithm assembly This page intentionally left blank, use if needed but it will not be marked.

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