Work Hours
Everyday: 北京时间8:00 - 23:59
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 endof-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 alinked 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 anordered 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 keys11,9, 7, 63, 13, 40, 33, 5, 39, 50are 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 calledpostorder_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. Eachprint 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, addtype 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
