THIS PAPER IS FOR STUDENTS STUDYING AT: (tick where applicable)
oCaulfield þClayton oParkville oPeninsula o Monash Extension o Off Campus Learning þ Malaysia o Sth Africa oOther (specify)
AUTHORISED MATERIALS OPEN BOOK CALCULATORS
SPECIFICALLY PERMITTED ITEMS if yes, items permitted are:
oYES þNO oYES þNO oYES þNO
Office Use Only
EXAM CODES:
TITLE OF PAPER:
EXAM DURATION:
READING AND NOTING TIME:
Semester One 2018 Examination Period
Faculty of Information Technology
FIT1008
Introduction to Computer Science – PAPER 1 2 hours writing time
30 minutes
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.
Candidates must complete this section if required to write answers within this paper
STUDENT ID: __ __ __ __ __ __ __ __ DESK NUMBER: __ __ __ __ __
Page 1 of 38
Question 1 [10 marks]
This question is about MIPS programming and function calls. Translate the following Python code faithfully into MIPS. Make sure you follow the MIPS function calling and memory usage conventions as discussed in the lectures. Use only instructions in the MIPS reference sheet. Notice that there is no code calling the function, thus the answer should involve only instructions executed by the callee.
Python Code
MIPS Code
def my_function(n, m):
if n == 0:
return m
else:
return m//n
Page 3 of 38
10
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22 23
Question 2 – Array-based structures [11 marks = 3 + 3 + 3 + 2]
This question is about Array-based structures. The partial implementation below is from a Queue whose underlying array is automatically resizable. The Queue uses the space of the array efficiently, by wrapping around the front and the rear indices (i.e. a circular queue). In addition, it doubles the size of the underlying array when appending to a Queue that is already using all the space available. The partial implementation is as follows:
class Queue:
def
def
def
def
def
__init__(self):
self.array = build_array(10) self.front = 0
self.rear = 0
self.count = 0
is_full(self): return False
is_empty(self):
return self.count == 0
__len__(self): return self.count
append(self, new_item):
if self.count == len(self.array):
self.__resize__()
self.array[self.rear] = new_item
self.rear = (self.rear+1) % len(self.array) self.count+=1
(a) Implement the method __resize__(self), which is used by the append function. This method should double the size of the underlying array. It should also, if necessary, re-arrange the values of the instance variables.
Page 5 of 38
3
(b) Implement the method serve(self), which serves an item out of the Queue. This method never modifies the size of the underlying array, and raises an Exception if empty.
(c) Implement the method __str__(self), which returns a string representing the Queue, including all elements, separated by comma, from the front to the rear. For example, a Queue with two elements 1 and 2, at the front and the rear respectively, is represented by the string “[1,2]”. An empty Queue will be “[]”.
(d) In Big O notation what is the best and worst case for appending to a Queue with n elements and when do the cases occur. Explain by giving an example for each case.
Page 7 of 38
8
Question 3 – Sorting Algorithms [9 marks = 3 + 3 + 3]
Consider the BubbleSort, InsertionSort, SelectionSort, MergeSort, QuickSort and Heap- Sort algorithms we have seen in the lectures, for sorting an array of length N. For those we have seen several versions (e.g. Bubble Sort) use the most efficient version we have seen.
(a) Name those (if any) that are not stable, and briefly explain why they are not stable.
(b) Name those (if any) that run in worst-case time O(N log N), and briefly explain how they manage to take O(N log N).
(c) Names those (if any) that run in best-case time O(N), and briefly explain how they manage to take O(N).
Page 13 of 38
9
1 2 3 4 5 6
Question 4 – Hashing [8 marks ]
You have started coding a HashTable as follows:
class MyHashTable:
def __init__(self, size):
self.table_size = size
self.array = build_array(self.table_size) self.count = 0
Assume you need to choose a hash function for your hash table. Each key to be hashed is a sequence of N integers, such as [10,3,5,3,20]. For example, a (key, value) pair to be stored could be ([10,3,5,3,20], “Introduction to CS”). You are given the following three possibilities to choose from.
(a) Returns the value of random.randint(0, self.table_size-1) (i.e., a random integer between 0 and the size of the table).
(b) Returns the minimum value in the sequence to be hashed (3 in our example above) mod size of the table.
(c) Returns the multiplication of all values in the sequence to be hashed (10*2*5*3*20 in our example above) mod size of the table.
For each function explain briefly what are the disadvantages. Rank the three possibilities from best to worst.
Page 15 of 38
8
Question 5 – Hash Tables [7 marks = 5 + 2 ] Consider a hash table implemented with an array of size 7.
(a) Show in the figure below (right) the final state of the array after inserting the numbers, 7, 3, 10, 5, 4, and 11. Collisions are resolved using linear probing with the hash function h(k) = k%7, provided in the table below.
key h(key) 0 701 332
103 3 554 445
114 6
(b) What is the load of your hash table once all the numbers have been inserted?
Page 17 of 38
7
1 2 3 4 5 6 7 8 9
10 11 12 13
Question 6 – Linked Lists [9 marks = 6 + 3]
Consider the following linked List class, which you are in the process of defining: class Node:
def __init__(self, item=None, link=None): self.item = item
self.link = link class List:
def __init__(self): self.head = None
def is_empty(self):
return self.head is None
Page 19 of 38
0
(a) Define a method copy(self) within the List class that returns a new linked list containing a copy of the nodes in self, in the given order and without modifying self. For example, given a_list with elements A,B,C, and D in the Figure above, the call to a_list.copy() will return the new list copy also shown in the figure, leaving a_list1 unchanged. If a_list is empty, a_list.copy() will return a new empty list. Do not assume the existence of other methods beyond those defined above.
Page 21 of 38
6
(b) Below is a partial implementation of an Iterator for the List class defined in part a.
1 2 3 4
class MyLinkedListIterator:
def __init__(self, head): self.current = head
Complete this iterator implementation by writing down the methods __next__(self) and __iter__(self).
Page 23 of 38
3
Question 7 – Data Structures and Complexity [8 marks]
Consider an unsorted list of N integers. Use Python to write a function that takes the list as a parameter and prints the elements that appear more than once. For example, for a list [6, 10, 6, 11, 6, 4, 5, 4], the algorithm will print 6 and 4. Your implementation should have worst case O(n) time complexity, where n is the size of the list. You can assume and use any sorting algorithm we have seen (bubble_sort, insertion_sort, selection_sort, merge_sort, quick_sort and heap_sort), and any data structure we have seen (List, Stack, Queue, HashTable, Heap) – without writing them, including any methods we have defined in class as part of each structure. Note: Do not worry about exact method names or parameters as long as they are indicative, we are interested in your algorithmic reasoning, not syntax details.
Page 25 of 38
8
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
Question 8 – Binary Trees [11 marks = 5 + 4 + 2]
Consider the partial implementation of BinarySearchTree class given below, which uses
the TreeNode class: class TreeNode:
def
__init__(self, key, value, left=None, right=None): self.item = (key, value)
self.left = left
self.right = right
class BinarySearchTree:
def
def
def
__init__(self): self.root = None
is_empty(self):
return self.root is None
LCA(self, key1, key2):
return self.LCA_aux(self.root, key1, key2)
(Only keys depicted)
If the method LCA is applied to the binary search tree above, LCA(self, 2, 5) will
return 3, LCA(self, 7, 4) will return 6, and LCA(self, 7, 8) will return 7.
Page 27 of 38
0
(a) The Lowest Common Ancestor (LCA) of two nodes x and y in a binary tree is the node with the lowest key that has both x and y as descendants. Assuming key1 and key2arebothintegers,implementthemethodLCA_aux(self, current, key1, key2) called from the method LCA(self, key1, key2) given above. The method returns
the key of the lowest common ancestor of Nodes containing key1 and key2. You can safely assume that key1 and key2 do exist, in other words, the precondition of the method is that key1 and key2 are part of the Binary Search Tree. See the examples above and notice that a node is its own ancestor as shown by the last example.
Page 29 of 38
5
(b) Implement the method traverse_preorder(self) within the BinarySearchTree class above. The method should return a Python list containing all the keys in the tree, as given by a pre-order traversal. For example, for the BST in the figure above the method returns [6, 3, 2, 4, 5, 9, 7, 8, 10]. You can use the usual append method to append an element to the end of the Python list. For an empty heap, it naturally returns the empty list.
(c) What is the best-case and worst-case time complexity of the most efficient imple- mentation of traverse_preorder(self)? Explain. No explanation, no marks.
Page 31 of 38
6
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21 22
Question 9 – Heaps [10 marks = 6 + 4]
Consider the partial implementation of MaxHeap class given below: class MaxHeap:
def
def
def
def
__init__(self):
self.array self.count
swap(self,
self.array[i], self.array[j] = self.array[j], self.array[i]
largest_child(self, k):
if 2 * k == self.count or self.array[2 * k][0] > self.array[2 * k + 1][0]:
return 2 * k else:
return 2 * k + 1
sink(self, k):
while 2 * k <= self.count:
child = self.largest_child(k)
if self.array[k][0] >= self.array[child][0]:
break self.swap(child , k) k = child
= build_array (50) =0
i, j):
The underlying array stores tuples (key, value). The examples below depict keys only.
Page 33 of 38
0
(a) Implement the method swap_children(self), which modifies the heap structure to swap the immediate children of every node (if any), sinking as necessary to keep the structure a valid max heap. For example, in the figures above, if the method is applied to the max heap on the left, it will modify it to be the one on the right.
(b) Draw the array behind a heap (using the convention seen in the lectures) after inserting the keys 15, 32, 17, 51, 29, 10, 23 into the max heap and then deleting 51 and 32 (no need to depict values, only keys).
Page 35 of 38
10
Question 10 – Classes, Objects, and Namespaces [8 marks] Examine the following Python code:
1 class Car: 2
3 numberOfTyre = 4
4 steeringLocation = “Left”
5 engineLocation = “Front”
6 regionCode = 1770174
7
8 def 9
__init__(self, brand, enginePower): self.brand = brand
self.enginePower = enginePower
10
11
12 def 13
14
15 def 16
17
18 car2 = Car(“Nissan”, 2400)
19 car2.setColour(“Green”)
20 car2.engineLocation = “Back”
21 car2.numberOfTyre = 6
22 car1 = Car(“Toyota”, 1000)
23 car1.setSeatNumber(3)
24 car1.steeringLocation = “Right”
25 car1.colour = “Red”
26 car1.regionCode = 1000000
27 print(car2.colour) #1
28 print(car1.colour) #2
29 print(car2.steeringLocation) #3
30 print(car1.engineLocation) #4
31 Car.numberOfTyre = 3
32 car1.enginePower = 500
33 print(car2.numberOfTyre) #5
34 print(car1.numberOfTyre) #6
35 print(car2.enginePower) #7
36 print(car1.seatNumber) #8
(a) Provide the result of each print statement (marked with comments from #1 to #8) – next to the comment above. If the results is an error, explain why assuming the execution will continue after executing the Python code above.
END OF EXAM.
setSeatNumber(self, numberOfSeat): self.seatNumber = numberOfSeat
setColour(self, colour): Car.colour = colour
Page 37 of 38
8