EXAM CODES: TITLE OF PAPER: TEST DURATION: READING TIME:
Monash University Semester Two Mid Semester Test 2016
Faculty of Information Technology
FIT1008
INTRODUCTION TO COMPUTER SCIENCE 35 minutes
5 minutes
THIS PAPER IS FOR STUDENTS STUDYING AT:
oBerwick oCaulfield oPharmacy
üClayton üMalaysia oGippsland oPeninsula oOther (specify)
oOff Campus Learning oEnhancement Studies
oOpen Learning oSth Africa
During an exam, you must not have in your possession, a book, notes, paper, electronic device/s, calculator, pencil case, mobile phone or other material/item which has not been authorised for the exam or specifically permitted as noted below. Any material or item on your desk, chair or person will be deemed to be in your possession. You are reminded that possession of unauthorised materials in an exam is a discipline offence under Monash Statute 4.1.
No examination papers are to be removed from the room.
AUTHORISED MATERIALS
CALCULATORS
OPEN BOOK
SPECIFICALLY PERMITTED ITEMS
o YES oYES oYES
ü NO üNO üNO
A – Official Use Only
STUDENT ID __ __ __ __ __ __ __ __
Page
Mark
3
5
7
9
Total
Page 1 of 9
This page intentionally left blank, use if needed but it will not be marked.
Page 2 of 9
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
Page 3 of 9
3
This page intentionally left blank, use if needed but it will not be marked.
Page 4 of 9
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
Page 5 of 9
2
This page intentionally left blank, use if needed but it will not be marked.
Page 6 of 9
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.
• Is quick-sort stable? Explain your answer. No explanation means no marks.
Page 7 of 9
3
This page intentionally left blank, use if needed but it will not be marked.
Page 8 of 9
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.
Page 9 of 9
3
Call code ($v0) 1
Service
Arguments
Returns
Notes
.data
.text
.byte b1[, b2, ...] .half h1[, h2, ...] .word w1[, w2, ...] .space n
.align n
.ascii ”string” .asciiz ”string”
4
string must be terminated with ’\0’ value is signed
5 8
Input integer Input string
-
$v0 = entered integer
–
9 10
Allocate memory Exit
$a0 = number of bytes
-
$v0 = address of first byte
-
-
On function return: Callee: Caller:
Number R00
R01
R02, R03 R04–R07 R08–R15 R16–R23 R24, R25 R26, R27 R28
Name
Purpose
provides constant zero
reserved for assembler
system call code, return value system call and function arguments temporary storage (caller-saved) temporary storage (callee-saved) temporary storage (caller-saved) reserved for kernel code
pointer to global area
stack pointer
frame pointer
return address
R29 R30 R31
$sp $fp $ra
Instruction Format
Rsrc, Rsrc1, Rsrc2: source operand(s), - must be a register value(s)
Src2; source operand - may be an immediate value or a register value Rdest: destination, must be a register
Imm: Immediate value, may be 32 or 16 bits
Imm16: Immediate 16-bit value
Addr: Address in the form: o↵set(Rsrc) ie. absolute address = Rsrc + o↵set label: label of an instruction
?: pseudoinstruction
Immediate Form -: no immediate form, or this is the immediate form
?: immediate form synthesized as pseduoinstruction
Unsigned form (append ’u’ to instruction name):
- : no unsigned form, or this is the unsigned form
Print integer Print string
$a0 = value to print
$a0 = address of string to print
- -
value is signed
assemble into text (code) segment
allocate byte(s), with initial value(s)
allocate halfword(s), with initial value(s) allocate word(s) with initial value(s)
allocate n bytes of uninitialized, unaligned space align the next item to a 2n-byte boundary allocate ASCII string, do not terminate
allocate ASCII string, terminate with ’\0’
Table 1: SPIM system calls
Table 3: Assembler directives assemble into data segment
$a0 = address to store string at
$a1 = max- imum number of chars
returns if $a1-1 charac- ters or Enter typed, the string is ter- minated with ’\0’
Caller:
Table 4: Function calling convention On function call:
Table 2: General-purpose registers
$zero
$at
$v0, $v1
$a0--$a3
$t0--$t7
$s0--$s7
$t8, $t9
$k0, $k1
$gp
Table 5: Instruction Set
FIT1008 Supplementary Material - MIPS Reference Sheet
ends simula- tion
sets $v0 to return value
clears local variables o↵ stack restores saved $fp and $ra o↵ stack returns to caller with jr $ra
clears arguments o↵ stack
restores temporary registers o↵ stack uses return value in $v0
saves temporary registers on stack passes arguments on stack
calls function using jal fn label
saves $ra and $fp on stack copies $sp to $fp
allocates local variables on stack
A partial instruction set is on the next page. The following conventions apply.
Page 1
Callee:
Table 6: MIPS instruction set
Instruction format
Meaning
Operation
Immediate form
Unsigned form(u)
add Rdest, Rsrc1, Rsrc2 sub Rdest, Rsrc1, Rsrc2 mul Rdest, Rsrc1, Rsrc2 ? mulo Rdest, Rsrc1, Rsrc2 ?
mult Rsrc1, Rsrc2
div Rdest, Rsrc1, Rsrc2 ? div Rsrc1, Rsrc2
rem Rdest, Rsrc1, Rsrc2 ? neg Rdest, Rsrc ?
Add
Subtract
Multiply
Multiply
(with 32-bit overflow) Multiply
(machine instruction) Divide
Divide
(machine instruction) Remainder
Negate
Rdest = Rsrc1 + Rsrc2 Rdest = Rsrc1 - Rsrc2 Rdest = Rsrc1 * Rsrc2 Rdest = Rsrc1 * Rsrc2
Hi:Lo = Rsrc1 * Rsrc2
Rdest=Rsrc1/Rsrc2
Lo = Rsrc1/Rsrc2;
Hi = Rsrc1 % Rsrc2 Rdest = Rsrc1 % Rsrc2 Rdest = -Rsrc1
addi
? ? ?
-
?
-
?
-
no overflow trap no overflow trap unsigned operands unsigned operands
unsigned operands
unsigned operands unsigned operands
unsigned operands no overflow trap
and Rdest, Rsrc1, Rsrc2 or Rdest, Rsrc1, Rsrc2 xor Rdest, Rsrc1, Rsrc2 nor Rdest, Rsrc1, Rsrc2 not Rdest, Rsrc ?
Bitwise AND Bitwise OR Bitwise XOR Bitwise NOR Bitwise NOT
Rdest = Rsrc1 & Rsrc2 Rdest = Rsrc1 | Rsrc2 Rdest = Rsrc1 ^ Rsrc2 Rdest = ⇠(Rsrc1 | Rsrc2) Rdest = ⇠(Rsrc)
Rdest = Rsrc1 << Rsrc2 Rdest = Rsrc1 >> Rsrc2 (MSB=0)
Rdest = Rsrc1 >> Rsrc2 (MSB preserved)
andi ori xori ?
– –
–
– – – – –
sll Rdest, Rsrc1, Rsrc2 srl Rdest, Rsrc1, Rsrc2
sra Rdest, Rsrc1, Rsrc2
Shift Left Logical Shift Right Logical
Shift Right Arithmetic
– –
–
move Rdest, Rsrc ? mfhi Rdest
mflo Rdest
Move
Move from Hi Move from Lo
Rdest=Rsrc Rdest = Hi Rdest = Lo
– – –
– – –
li Rdest, Imm ?
lui Rdest, Imm16
la Rdest, Addr(or label) ?
Load immediate
Load upper immediate Load Address
Rdest=Imm Rdest=Imm16 << Imm Rdest=Addr
(or Rdest=label)
- - -
- - -
lb Rdest, Addr (or label ?) lh Rdest, Addr (or label ?) lw Rdest, Addr (or label ?)
Load byte Load halfword Load word
Rdest = mem8[Addr] Rdest = mem16[Addr] Rdest = mem32[Addr]
- - -
zero-extends data zero-extends data -
sb Rsrc2, Addr (or label ?) sh Rsrc2, Addr (or label ?) sw Rsrc2, Addr (or label ?)
Store byte Store halfword Store word
mem8[Addr] = Rsrc2 mem16[Addr] = Rsrc2 mem32[Addr] = Rsrc2
- - -
- - -
beq Rsrc1, Rsrc2, label bne Rsrc1, Rsrc2, label blt Rsrc1, Rsrc2, label ? ble Rsrc1, Rsrc2, label ? bgt Rsrc1, Rsrc2, label ? bge Rsrc1, Rsrc2, label ? slt Rdest, Rsrc1, Rsrc2
Branch if equal
Branch if not equal Branch if less than
Branch if less than or equal Branch if greater than
Branch if greater than or equal
Set if less than
if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 Rdest=1
== Rsrc2) label
!= Rsrc2) label
< Rsrc2) label
<= Rsrc2) label
> Rsrc2) label
>= Rsrc2) label
< Rsrc2) else Rdest=0
?
?
?
?
?
? slti
-
-
unsigned operands unsigned operands unsigned operands unsigned operands unsigned operands
j label jal label
jr Rsrc jalr Rsrc
Jump
Jump and link
Jump register
Jump and link register
PC = label $ra = PC + 4; PC = label PC = Rsrc $ra = PC + 4; PC = Rsrc
- -
- -
- -
- -
syscall
System call
depends on call code in $v0
-
-
Page 2