EXAM CODES: TITLE OF PAPER: EXAM DURATION:
Rules
FIT1008-FIT2085
Introduction to Computer Science 3 hours 10 mins
Semester One 2019 Examination Period
Faculty of Information Technology
During an exam, you must not have in your possession any item/material that has not been authorised for your exam. This includes books, notes, paper, electronic device/s, mobile phone, smart watch/device, calculator, pencil case, or writing on any part of your body. Any authorised items are listed below. Items/materials on your desk, chair, in your clothing or otherwise on your person will be deemed to be in your possession.
No examination materials are to be removed from the room. This includes retaining, copying, memorising or noting down content of exam material for personal use or to share with any other person by any means following your exam.
Failure to comply with the above instructions, or attempting to cheat or cheating in an exam is a discipline offence under Part 7 of the Monash University (Council) Regulations, or a breach of instructions under Part 3 of the Monash University (Academic Board) Regulations.
Authorised Materials
OPEN BOOK
CALCULATORS
SPECIFICALLY PERMITTED ITEMS if yes, items permitted are:
Instructions
YES NO YES NO YES NO
Please answer all questions online. Noting and calculations to be done in the scriptbook or working sheets provided.
Instructions
Information
Please answer all questions online. Noting and calculations to be done in the scriptbook or working sheets provided.
MIPS reference sheet
Information
Python to MIPS translation
Question 1
Translate the following Python code faithfully into MIPS assembly language. Make sure you follow the MIPS function calling and memory usage conventions.
We ask that you translate this codeinstruction by instruction, using the sub-questions below. The concatenation of all 6 answers must correspond to the entire translation of the Python code above.
Comments are not mandatory and will not be marked, but will help us understand your code and, in that way, can help you get extra points. Use ‘#’ at the start of a line in your MIPS code to add a comment.
17
Marks
def func (n): if n <= 0:
result = 0 else:
result = 4*n+func(n-1) return result
def func (n):
if n <= 0:
result = 0
result = 4*n+func(n-1)
return result
else:
The Python function above can easily be implemented iteratively, rather than recursively. Assume the iterative version uses N bytes of Heap memory. What value is N and how many bytes will the recursive version use? Explain why (no explanation no marks).
Assume now that the iterative version uses N bytes of Stack memory. What value is N and how many bytes will the recursive version use? Explain why (no explanation no marks).
Scoping with classes in Python
Question 2
You are provided with the Pythonmyclass.py module:
10
Marks
class myclass:
def __init__(self,x):
self.x = x def a(self):
self.x = self.x + 1 def b(self):
self.x = x + 2 def c(self):
x = self.x + 3 def __str__(self):
return str(self.x) def a(x):
x=x-1
def b(): x=x+2
This module will be imported in each of the following questions. In each of the following questions, there will be exactly one print statement. We ask that you find the value being printed by each piece of code.
For example, if the question is: Then your answer should be: 1.
Pick one answer in this column for each of the boxes on the left
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
print(1)
from myclass import * myobject = myclass(1) print(myobject)
from myclass import * x=2
myobject = myclass(x) x=1
print(myobject)
from myclass import * myclass.x = 3 myobject = myclass(2) print(myobject)
from myclass import * myobject = myclass(3) myclass.x = 4 print(myobject.x)
from myclass import * myclass.x = 6
myobject = myclass(myclass.x) a(myclass.x) print(myobject.x)
from myclass import * x=5
myclass.x = 3 print(myclass(1).b())
from myclass import * x=7
myobject = myclass(x) myobject.c()
print(x)
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
• 7 • 4 • No output. The code produces an error. • 3 • 0 • 8 • 5 • 6 • None • 2 • 10 • 1 • 9
from myclass import * x=6
b()
myobject = myclass(x) myobject.a() print(myobject)
from myclass import * x=2 print(myclass(a(x)))
from myclass import *
x=0
myobject = myclass(x)
yourobject = myclass(myobject.x) myobject.c()
a(yourobject.x) print(yourobject)
CS saves the world
Question 3
Year 2069. A malevolent alien species who speaks in Python has sent the following message to Earth:
20
Marks
def mystery(x): y=x%2
x = x // 2 if x > 0:
y = y + mystery(x) return y
def enigma(x):
y = mystery(x)
if y > 1:
y = y + enigma(y)
return y
#puny humans must print:
print(enigma(4095))
If we do not compute and send them the result of enigma(4095) within the next 3 hours (plus 10 minutes of reading), the aliens have promised that they would destroy the planet. As Earth’s leading computer scientist, the task of saving humanity naturally lies with you. Your former esteemed FIT1008&2085 lecturers, recently retired, have advised you to first answer a series of questions before attempting to compute the final result.
Write the output of the function mystery for the input values:
x=1 x=2 x=3 x=7 x=8 x=15
What does the function mystery compute?
What is the time complexity of mystery, using the O() notation? Prove your answer.
Write the output of the function enigma for the input values:
x=1 x=2 x=3 x=7 x=8
x = 15
What does the function enigma compute?
What is the best and worst time complexity of enigma, using the O() notation? Prove your answer. What does enigma(4095) return? Justify your answer.
Natural merging
Question 4
In this question we suppose that all sorting is done in a non-decreasing way.
We propose to write a new sorting algorithm that first detects when part of the data is already sorted. For example, if the input list is [0, 4, 1, 2, 8, 5, 7, 9, 3, 6], then the algorithm will first detect the consecutive items that are already sorted, namely [0, 4], [1,2,8], [5,7,9] and [3,6].
After this, the algorithm will merge these sublists two by two until the entire list is sorted.
Write a function find_intervals which, given a list as input, returns the list of indices between which the input list is already sorted. For our example list, the output would be [0, 2, 5, 8, 10], since the list is sorted between indices 0 and 1, 2 and 4, 5 and 7, 8 and 9. Note that the last index in the output list (10) points outside of the input list.
We ask that you use this template:
In the code above, the variable separators refers to the list of indices that you must return. You may use any Python built-in method for this function.
14
Marks
def find_intervals(list): separators = [0] #TODO your code here return separators
def find_intervals(l): separators = [0] #TODO your code here
return separators
What is the worst-case time complexity of the find_intervals function you have written? Explain your answer.
Write a function natural_merge which takes the list to sort as an input and sorts it. This function must call the previous function to determine intervals which are already sorted. You will not be penalised if you have not attempted or succeeded the previous questions. For this question you will be marked as if the previous questions had been answered correctly.
The function natural_merge must implement the following algorithm:
1. Find the intervals of the input list where the data is already sorted by calling the previous function.
2. Iterate through the list and merge the first and the second interval together. After the merge,
these two intervals become a single interval, hence there is one fewer interval in the list. This continues until there is only a single interval left. For example, for our input list, we would obtain the following steps:
[0, 4] [1, 2, 8] [5, 7, 9] [3, 6] and interval list [0, 2, 5, 8, 10] [0, 1, 2, 4, 8] [5, 7, 9] [3, 6] and interval list [0, 5, 8, 10]
[0, 1, 2, 4, 5, 7, 8, 9] [3, 6] and interval list [0, 8, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and interval list [0, 10]
To do the merging, you must call the function merge provided below:
Although we provide the code, you only need to call the function merge according to its documentation. Write the function natural_merge below:
def natural_merge(l):
What is the worst-case time complexity of the merge function we have provided? Explain your answer.
What is the best-case time complexity of the algorithm natural_merge? Explain your answer. You may answer this question based on the description we provide of it, even if you have not implemented it.
What is the worst-case time complexity of the algorithm natural_merge? Explain your answer. You may answer this question based on the description we provide of it, even if you have not implemented it.
How could a sorting algorithm with better time complexity be designed using the ideas presented in this question? Explain your answers.
def merge(l, start, mid, end):
“””Merges the two sorted sublists of l
between start and mid (excluded)
and mid and end (excluded) “””
tmp = [None] * (end-start) k1 = start
k2 = mid
use1 = False
for k in range(start, end): if k1 >= mid:
use1 = False elif k2 >= end: use1 = True
else:
use1 = (l[k1] <= l[k2])
if use1 is True: tmp[k] = l[k1]
k1 += 1 else:
tmp[k] = l[k2]
k2 += 1
for k in range(start, end):
l[k] = tmp[k]
Resolving collisions
Question 5
Suppose you are given the following set of keys to insert into a Hash table of size 11: 22 , 23 , 37, 29, 33, 39, 2, 27, 21, 17.
The hash function is given below.
Suppose that we use linear probing with a skip of k=1 to resolve collisions. Select the correct state of the Hash Table after the keys have been inserted.
Select one:
22, 23, 33, 2, 37, 27, 39, 29, 17, None, 21
22, 23, 37, 29, 33, 39, 2, 27, 21, 17
29, 37, 17, 33, 21, 2, 39, 23, 22, None, 27
39, 2, 22, 17, 23, 37, 29, None, 33, 21, 27
2, 37, None, 17, 23, 29, 39, 27, 33, 21, 22
None, 2, 23, 21, 39, 33, 29, 22, 27, 37, 17
22, 23, 37, 29, 33, None, 27, 39, 17, 21, 2
17, 21, None, 2, 29, 23, 27, 22, 39, 33, 37
37, 2, 21, 29, 22, 33, None, 23, 17, 27, 39
21, 2, 22, 37, 39, 17, 23, 29, 33, 27, None
33, 29, 27, 37, 2, 22, 17, 21, None, 23, 39
There is no correct state. Not all keys can be inserted. 22, 23, 2, None, 37, 27, 39, 29, 17, 33, 21
22, 23, 2, 17, 37, 27, 39, 29, None, 33, 21
22, 23, 2, 33, 37, 27, 39, 29, 17, None, 21
22, 23, None, 2, 37, 27, 39, 29, 17, 33, 21
22, 23, 2, None, 37, 27, 39, 29, 17, 33, 21
2
Marks
def hash_function(key): return key%11