Question 1 [3 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.
a=3
b=5
c=0
while b > a:
if b % 2 == 0: c=c+b
else:
c = c -b
b = b-1
.data
a: .word 0
b: .word 0
c: .word 0
.text
main:
add $fp, $sp, $0 li $t0, 3
sw $t0, a
li $t0, 5
sw $t0, b
sw $0, c while:
lw $t0, b
lw $t1, a
sgt $t0 , $t0 , $t1
beq $t0 , $0, endwhile
if: lw $t0, b li $t1, 2
div $t0 , $t1 mfhi $t0
bne $t0 lw $t0, lw $t1, add $t0 sw $t0, j endif
else:
lw $t0,
lw $t1, sub $t0 sw $t0,
endif:
lw $t0,
li $t1, sub $t0 sw $t0, j while
endwhile: li $v0,
syscall
, $0, else c
b c
c b
c
b 1
b
10
,
,
,
$t0 , $t1
$t0 , $t1
$t0 , $t1
Page 3 of 6
3
0.5 marks for faithful code (no reusing registers, every python line addressed). 0.5 marks for declaring global variables in text segment.
1 mark for correct implementation of loops using MIPS.
1 mark for correct implementation of decisions using MIPS.
Question 2 [2 marks]
For each function below, provide best and worst case complexity in Big O notation. Explain your answer – no explanation means no marks.
1. def
2. def
function_a(a_list):
n = len(a_list)
for i in range(n-1, -1, -1):
for j in range (10): a_list[i] = j + i- 1
function(a_list):
n = for
len(a_list)
j in range(n):
i=j
while a_list[i] < 0:
a_list[i] = j + i- 1
i=i-1 a_list[j] = i
1. Best and Worst O(N) where N is the length of the list. The outer loop is dependent on the size of the list, there’s no early exit condition. The inner loop runs a fixed amount of time, with constant operations. Therefore the overall complexity is O(N).
0.5 correct best case with explanation and 0.5 correct worst case with explanation.
2. Best and Worst O(N) where N is the length of the list Best case: O(N) where the list has all position values. In this case the outer loop iterates N times and it doesn’t enter the inner loop. Worst case: O(N2) when the list has all negative values. In this case the tightest upper bound is N ∗ N, as the inner loop runs up to N times.
0.5 correct best case with explanation and 0.5 correct worst case with explanation.
Question 3 [3 marks]
A quick-sort implementation is given below:
def quick_sort(a_list): start = 0
end = len(a_list) -1 quick_sort_aux(a_list, start, end)
def quick_sort_aux(a_list, start, end): if start < end:
boundary = partition(a_list, start, end) quick_sort_aux(a_list, start, boundary-1) quick_sort_aux(a_list, boundary+1, end)
• Write a method partition, that completes this implementation. Your partition algorithm should have linear time complexity.
Page 4 of 6
def swap(a_list , a b):
a_list[a], a_list[b] = a_list[b], a_list[a]
def partition(a_list, start, end): boundary = start
pivot = a_list[boundary]
for i in range(start + 1, end + 1):
if a_list[i] < pivot:
swap(a_list , boundary + 1, i) boundary += 1
swap(a_list , boundary , start) return boundary
0.5 concept implementation of the partition, pivot in the middle 0.5 linear running time
1 correct partition
• Is quick-sort stable? Explain your answer. No explanation means no marks. No, because when you swap elements you could change the relative order of elements with the same key.
1 mark correct answer and explanation.
Question 4 [2 marks]
Consider the following python code, which you wish to translate into MIPS.
a=2 b=3
def my_function(a, b): i=a
# HERE
while i < b:
a=a+b
i +=1 return a
my_function(a, b)
Draw the memory diagram of the stack segment when code execution reaches the line marked with the comment HERE. The diagram should show, the stack pointer and frame pointer and any information that may be stored as part of the function calling convention discussed in the lectures. Global variables are not on the stack, so they are not to be shown. Before reaching my_function, ra = 0x00400000 and fp = 0x7FFFB3114.
===== 2 | ===== $fp‘| ===== $ra‘| ===== 3 | ===== 2 | =====
i ($sp) (0x7FFFB3104)
$fp‘ = 0x7FFFB3118 ($fp = 0x7FFFB3108) $ra‘ = 0x7FFFB3110 (0x7FFFB310C)
b (0x7FFFB3110)
a (0x7FFFB3114)
Page 5 of 6
3
0.5 marks, local variables, arguments + ra and fp in stack (5 elements exactly). 0.5 marks, arguments below ra and fp
0.5 marks, local variable i above fp
0.25 stack pointer points to top of stack
0.25 frame pointer points to saved fp
No need to list the addresses next to each block.
Page 6 of 6