2020 Semester Two (November-December 2020)
Examination Period
Faculty of Information Technology
EXAM CODES: FIT1008-FIT2085
TITLE OF PAPER: Intro to comp science
EXAM DURATION: 3 hours 10 mins
Rules
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.
You must not retain, copy, memorise or note down any exam content for personal use or to share with any other person by any means
following your exam.
You must comply with any instructions given to you by an exam supervisor.
As a student, and under Monash University’s Student Academic Integrity procedure, you must undertake your in-semester tasks, and end-
of-semester tasks, including exams, with honesty and integrity. In exams, you must not allow anyone else to do work for you and you must
not do any work for others. You must not contact, or attempt to contact, another person in an attempt to gain unfair advantage during your
exam session. Assessors may take reasonable steps to check that your work displays the expected standards of academic integrity.
Failure to comply with the above instructions, or attempting to cheat or cheating in an exam may constitute a breach of instructions under
regulation 23 of the Monash University (Academic Board) Regulations or may constitute an act of academic misconduct under Part 7 of the
Monash University (Council) Regulations.
Authorised Materials
OPEN BOOK YES NO
CALCULATORS YES NO
DICTIONARIES YES NO
NOTES YES NO
SPECIFICALLY PERMITTED ITEMS YES NO
if yes, items permitted are:
Page 1 of 17
Instructions
Marks
There are 100 marks in this exam. The exam is worth 60% of the unit mark.
MIPS code:
All translations from Python to MIPS must be faithful.
Only the instructions in the MIPS reference sheet (in appendix) are allowed.
The conventions given in the MIPS reference sheet must be followed.
Python code:
Unless otherwise specified, do not write type hinting, documentation, assertions or exceptions.
Write comments if necessary for understanding the code.
Complexity:
By default, "runtime complexity" refers to worst-case runtime complexity, which we ask you to express using the O( ) notation.
Page 2 of 17
Instructions
Information
Marks
There are 100 marks in this exam. The exam is worth 60% of the unit mark.
MIPS code:
All translations from Python to MIPS must be faithful.
Only the instructions in the MIPS reference sheet (in appendix) are allowed.
The conventions given in the MIPS reference sheet must be followed.
Python code:
Unless otherwise specified, do not write type hinting, documentation, assertions or exceptions.
Write comments if necessary for understanding the code.
Complexity:
By default, "runtime complexity" refers to worst-case runtime complexity, which we ask you to
express using the O( ) notation.
Page 3 of 17
Implementations of the Set ADT
Information
We consider the Set ADT studied in the workshop:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Set(ABC, Generic[T]):
""" Abstract class for a generic Set. """
def __init__(self) -> None:
""" Initialization. """
self.clear()
@abstractmethod
def __len__(self) -> int:
""" Returns the number of elements in the set. """
pass
@abstractmethod
def is_empty(self) -> bool:
""" True if the set is empty. """
pass
@abstractmethod
def clear(self) -> None:
""" Makes the set empty. """
pass
@abstractmethod
def __contains__(self, item: T) -> bool:
""" True if the set contains the item. """
pass
@abstractmethod
def add(self, item: T) -> None:
""" Adds an element to the set. Note that an element
already
present in the set should not be added.
"""
pass
@abstractmethod
def remove(self, item: T) -> None:
""" Removes an element from the set. An exception should be
raised if the element to remove is not present in the set.
"""
pass
We are interested in two different implementations of this ADT and their complexities.
Question 1
Suppose that we use an implementation of the Set ADT based on a linked list (which is not ordered).
Give the runtime complexities of each of the class methods of Set for this implementation. No
explanation, no marks.
6
Marks
Page 4 of 17
Question 2
Suppose that we use an implementation of the Set ADT based on an ordered array, which means that
the internal array is kept ordered at all times:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class ASet(Set[T]):
"""Implementation of the set ADT using an ordered array.
Attributes:
size (int): number of elements in the set
array (ArrayR[T]): array storing the elements of the set
ArrayR cannot create empty arrays. So default capacity value 1
is used to avoid this.
"""
def __init__(self, capacity: int = 1) -> None:
""" Initialization. """
Set.__init__(self)
self.array = ArrayR(max(1, capacity))
Give the runtime complexities of each of the class methods of Set for this implementation. No
explanation, no marks.
6
Marks
Page 5 of 17
Hash Tables
Question 3
Consider a hash table of size tablesize=11, with the hash function:
hash(key) = key % tablesize
Starting from an empty hash table, the keys 11,9, 7, 63, 13, 40, 33, 5, 39, 50 are inserted in the table in
that order. Using Linear Probing as the method of collision resolution, and the hash function shown
above, write the content of the hash table as a list. Separate the keys using commas and denote an
empty slot using quotation marks (""), for instance [ x, "", y, ... ]. You must also explain each insertion
step by step. No explanation, no marks.
5
Marks
Page 6 of 17
Sorting
Question 4
Describe Selection Sort in a few sentences. How can we make Selection Sort stable? Give a precise
description. How does this affect the worst-case runtime complexity? Give a proof. No proof, no
marks.
6
Marks
Question 5
Describe Quicksort in a few sentences. What is the best and worst case runtime complexity of
Quicksort? Give a proof of both of these. No proof, no marks. 6
Marks
Page 7 of 17
Heaps
Question 6
What are the advantages and disadvantages, if any, of an implementation of a heap that uses an array,
rather than a binary tree made of linked nodes? 4
Marks
Question 7
Consider the partial implementation of a max heap, as seen in the lessons:
1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import Generic
from referential_array import ArrayR, T
class Heap(Generic[T]):
MIN_CAPACITY = 1
def __init__(self, max_size: int) -> None:
self.length = 0
self.the_array = ArrayR(max(self.MIN_CAPACITY, max_size) +
1)
def __len__(self) -> int:
return self.length
Write a recursive method called postorder_list() inside the Heap class above that returns a list of the
content of the heap binary tree in postorder traversal. Recall that in a postoder traversal of a binary
tree,
First, the left subtree is traversed recursively in postorder
Second, the right subtree is traversed recursively in postorder
Third, the current node is processed (in our case, this simply means that the value at the node is
printed).
For example, it will return [2, 10, 15, 4, 5, 20] for the following Heap instance:
6
Marks
Page 8 of 17
Iterators
Question 8
Write an iterator to generate the Fibonacci sequence. Recall that the Fibonacci sequence is
1,1,2,3,5,8,13,21, ...
Use the template:
1
2
3
4
5
6
class FibIterator:
def __init__(self) -> None:
def __iter__(self) ->
FibIterator:
def __next__(self) -> T:
8
Marks
Page 9 of 17
Scoping
Question 9
In this question you are tasked to determine what is printed by a code. Each print instruction prints a
Python variable that refers to a function. For example, the code
1
2
3
4
5
6
class Mystery:
def f(self):
print(f)

f = Mystery()
f.f()
prints 1 Python object, which is the function defined at line 2 (remember that in Python, functions are
objects!). For the code below, write which functions (referring to them by the line at which they are
defined) are printed, in the correct order. Justify each answer. No justification, no mark.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Mystery:
def f(self):
def g():
print(f)
def h():
def f():
print(f)
f()
g()
h()

f = Mystery()
f.f()
5
Marks
Page 10 of 17
Stack ADT and sorting
Question 10
The problem consists in sorting a stack with the help of an auxiliary stack, and no other container.
Recall that the ADT of a Stack is:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class StackADT(ABC, Generic[T]):
def __init__(self) -> None:
self.length = 0
@abstractmethod
def push(self, item: T) -> None:
""" Pushes an element to the top of the stack."""
pass
@abstractmethod
def pop(self) -> T:
""" Pops an element from the top of the stack."""
pass
@abstractmethod
def peek(self) -> T:
""" Pops the element at the top of the stack."""
pass
def __len__(self) -> int:
""" Returns the number of elements in the stack."""
return self.length
def is_empty(self) -> bool:
""" True if the stack is empty. """
return len(self) == 0
@abstractmethod
def is_full(self) -> bool:
""" True if the stack is full and no element can be pushed. """
pass
def clear(self):
""" Clears all elements from the stack. """
self.length = 0
Given one input stack and one temporary stack, write a Python program that sorts the input stack,
using the temporary stack (no other containers) and without calling Python's sorting methods in any
way. Comment your code. For reference, there is a solution that has fewer than 12 lines (excluding
comments).
8
Marks
Page 11 of 17
The Bisection Algorithm
Information
We now attempt to answer a few questions related to the bisection method for finding the square root
of a number x, which we denote x½. We provide the description of the recursive version of this
algorithm here.
The input of this algorithm is:
x, a real number >= 0 that we must find the root of.
l, a lower bound on x½, i.e. l <= x½. Also l >= 0.
u, an upper bound on x½, i.e. x½ <= u. Also l <= u.
e, a numerical tolerance, i.e. the output y of the algorithm should satisfy |y-x½| <= e.
The bisection algorithm relies on the assumption that the root that we are looking for, x½, is in the
interval [l, u] at the start of the algorithm. It recursively divides the interval by 2, and selects the half in
which x½ is located by adjusting the values of l and u, until the interval is small enough to satisfy |u-l|
<=e, at which point u can be output with the guarantee that |u-x| <= e.
A Python implementation of the bisection algorithm that uses recursion to compute x½ is:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bisection_rec(x, l, u, e):
# base case
if u - l <= e:
return u
# compute the middle point of the interval [l,u]
m = (u+l)/2
# compute its square
s = m*m
# check how to divide the interval
if s >= x:
u = m
else:
l = m

# recurse
return bisection_rec(x, l, u, e)
Make sure that you understand this algorithm as it will be used in a few questions. The questions
are independent of each other and can be attempted in any order.
Examples of calls and returned values are given below:
bisection_rec(2, 0, 2, 0.0001) -> 1.41424560546875
bisection_rec(2, 0, 2, 0.1) -> 1.4375
bisection_rec(4.0, 0, 4.0, 0.0001) -> 2.0
Page 12 of 17
Question 11
The Python code we have provided does not have type hinting, documentation or assertions (in this
question we ignore exceptions). We provide the original code again for convenience:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bisection_rec(x, l, u, e):
# base case
if u - l <= e:
return u
# compute the middle point of the interval [l,u]
m = (u+l)/2
# compute its square
s = m*m
# check how to divide the interval
if s >= x:
u = m
else:
l = m

# recurse
return bisection_rec(x, l, u, e)
Based on the description of the algorithm and the code itself, add type hinting, documentation
(description, pre- and post-conditions) and assertions to match. Do not add exceptions, but for the
purpose of this question add assertions where you may normally add an exception.
8
Marks
Question 12
Extend the function we have provided to handle an extra argument n and to compute and return the
n^th root of x (rather than the square root). We provide the original code again for convenience:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bisection_rec(x, l, u, e):
# base case
if u - l <= e:
return u
# compute the middle point of the interval [l,u]
m = (u+l)/2
# compute its square
s = m*m
# check how to divide the interval
if s >= x:
u = m
else:
l = m

# recurse
return bisection_rec(x, l, u, e)
3
Marks
Page 13 of 17
Question 13
In this question we want to determine the runtime complexity of the bisection algorithm. We provide
the original code again for convenience:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bisection_rec(x, l, u, e):
# base case
if u - l <= e:
return u
# compute the middle point of the interval [l,u]
m = (u+l)/2
# compute its square
s = m*m
# check how to divide the interval
if s >= x:
u = m
else:
l = m

# recurse
return bisection_rec(x, l, u, e)
We denote L = (u - l) the length of the search interval and N = L/e the number of intervals
corresponding to the base case.
Express the worst-case runtime complexity of this algorithm as a function of N. Justify your answer.
5
Marks
Question 14
In this question we ask that you write the iterative version of the recursive bisection. We provide the
original code again for convenience:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def bisection_rec(x, l, u, e):
# base case
if u - l <= e:
return u
# compute the middle point of the interval [l,u]
m = (u+l)/2
# compute its square
s = m*m
# check how to divide the interval
if s >= x:
u = m
else:
l = m

# recurse
return bisection_rec(x, l, u, e)
Give a direct translation using the template provided.
8
Marks
Page 14 of 17
Question 15
Faithfully translate into MIPS the (modified) bisection function. Do not translate the body of the
original function. Only translate the code below:
1
2
3
4
5
6
def bisection_rec(x, l, u, e):
#the body is empty. Nothing to translate
here.
# recurse
return bisection_rec(x, l, u, e)
Recall that in MIPS, a recursive call can be translated as any other function call. Start the translation
with a stack diagram written as comments at the point of line 3's execution (the translation assumes
no body). The clarity of the MIPS code you write will be assessed together with its correctness and
faithfulness.
16
Marks
Page 15 of 17
Appendix
Information
Page 16 of 17
Page 17 of 17





















































































































































































































































































































































































































































































































































































































































学霸联盟