UNIVERSITY OF TORONTO

Faculty of Arts & Science

April 2022 Examinations

CSC 148 H1S Do not turn this page

until you have received the signal to start.
Duration: 3 hours In the meantime,
please fill out the section below,
Aids Allowed: Provided aid sheet
and carefully read all instructions on this page.

Given Name(s):

Family Name(s):

Student Number (9 or 10 digits): UTORid (e.g., pitfra12):

• Turn off and place all cell phones, smart watches, electronic devices, and unau-
thorized study materials in your bag under your desk. If it is left in your pocket,
Marking Guide
it may be an academic offence.
• This final examination consists of 11 questions on 18 pages (including this one), No 1: /13
printed on both sides of the paper. When you receive the signal to start, please
make sure that your copy of the examination is complete. No 2: / 4

• Answer each question directly on the examination paper, in the space provided. No 3: / 5
There are several blank pages at the end for rough work. No 4: / 4
• Comments are not required in your code, however they may help us give you part No 5: / 5
marks if your answer is not completely correct.
No 6: /10
• There is an aid sheet on a separate piece of paper. Nothing you write on the
aid sheet will be marked. No 7: / 6

• Remember that, in order to pass the course, you must achieve a grade of at least No 8: / 5
40% on this final examination. No 9: / 8
• As a student, you help create a fair and inclusive writing environment. If you No 10: / 5
possess an unauthorized aid during an exam, you may be charged with an
academic offence. No 11: /11

TOTAL: /76
It’s been a real pleasure teaching you this term. Good luck!

students must hand in this examination booklet at the end

 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 1. [13 marks]

Part (a) [4 marks]
Here’s a tiny bit of code we’ve just started. It has a problem that causes client code to raise an error.
class TransitSystem: class Bus:
def __init__(self, how_many: int) -> None: def __init__(self) -> None:
self.vehicles = [] self.model = ‘ProMaster CS-2’
for _ in range(how_many): self.year = 2020
self.vehicles.append(Bus)
1. Fix the problem by modifying the code above. Do not make more changes than necessary.
2. Assume our code is working now. Write a line of client code that makes an instance of TransitSystem
with 105 buses and assigns it to the variable ttc.

3. Write a line of code to print the model of the first bus in ttc (the one at index 0).

4. What is the technical term for the relationship between our two classes?

Part (b) [2 marks]

Write 2 lines of code to go in the space below so that all the asserts will succeed:

a = [[5, 6, 7], [3, 4, 1]]

assert a[0] is b[0]

assert a[1] is not b[1]
assert a[1] == b[1]
assert a is not b
assert c is a

Part (c) [2 marks] Suppose I can run this nonsense code without error:
thing1 = Froogle()
thing2 = Froogle()
thing1.absorb([1, 2, 3])
n = int(input(’Enter a number: ’)) # Read an int from the user.
if n in thing1:
thing2.absorb([n, n + 1, n + 2])
if thing1 == thing2:
print(f’{thing1} and {thing2} are samesies!’)
What method(s) must be defined in class Froogle so that the code runs? (It need not do anything sensible.)
April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Part (d) [3 marks]

Suppose we have imported the RecursiveList class from the aid sheet and executed the following code:

>>> pokey = RecursiveList([])

>>> small = RecursiveList([13])
>>> linky = RecursiveList([10, 20, 30, 40])

What is the value of each of the following expressions? If it raises an error, explain why the error occurs.

Expression Value (or description of error)

type(pokey._rest)

pokey._first == pokey._rest

small._rest._first is None

type(small._rest)

type(linky._first._rest)

linky._rest._rest._rest._first

Part (e) [2 marks]

Suppose we have imported the BinarySearchTree class from the aid sheet and executed the following code:

>>> b = BinarySearchTree(8)
>>> b.insert(20)
>>> b.insert(17)
>>> b.insert(2)

What is the value of each of the following expressions? If it raises an error, explain why the error occurs.

Expression Value (or description of error)

type(b._left._left)

b._right._left._root

b._right._right is None

b._root._left < b._root

 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 2. [4 marks]
Part (a) [2 marks]
For this question, fill in actual numbers, not formulas.

A binary search tree with 14 nodes has height at least and at most .

A general tree with 14 nodes has height at least and at most .

Part (b) [1 mark]

Here is a tree:

4663
8
it 5 Iq
0
It 3 8 44
d
2
The post-order traversal of this tree is:

Part (c) [1 mark]

Here is a tree:

234 Yg 2
1
70
68 3

If this tree is stored using our implementation of the BinarySearchTree class (see the Aid Sheet for reference),
how many instances of BinarySearchTree are used?
April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 3. [5 marks]
Part (a) [4 marks]
Complete the memory model diagram below to reflect the state of this code immediately before it is done
executing. Show the whole history of changes. For any values that change, cross out the old value and write the
updated value beside it. For popped stack frames, neatly cross out the stack frame by drawing an X over it.

def do_something(lst: List[List[int]]) -> None:

for sublst in lst:
sublst.append(99)

if __name__ == ‘__main__’:
original_lst = [[1, 2, 3], [4, 5, 6]]
lst_copy = [original_lst[0], original_lst[1]]
do_something(lst_copy)

Part (b) [1 mark]

What would be the output of the following two lines if we added them to the end of the code above?

print(original_lst)
print(lst_copy)
 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 4. [4 marks]
Consider the following module:

from typing import Dict

def bumbly(d: Dict) -> int:

try:
spot = mia(d)
return d[spot]
except KeyError:
print(‘something went wrong’)
return -1

def mia(d: Dict) -> int:

try:
place = chirly(d)
return d[place]
except KeyError:
print(‘something went wrong’)
return -1

def chirly(d: Dict) -> int:

try:
return sum(d.values())
except KeyError:
print(‘something went wrong’)
return -1

if __name__ == ‘__main__’:
d = {3: 8, 5: 32, 0: 2}
answer = bumbly(d)
print(answer)

Answer these questions about the code:

1. There is an error which occurs in the code above, but is handled by one of the try..except clauses. In
which function does this error occur? Circle one:
(a) bumbly
(b) mia
(c) chirly
(d) None of the above
April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

2. For each of the following, circle YES or NO to indicate whether or not it has a stack frame on the call
stack at the moment when the error occurs.

bumbly YES NO
mia YES NO
chirly YES NO
__main__ YES NO

3. What is a key-value pair that could be added to the dictionary d above (before calling the bumbly function
in the main code) to prevent any KeyError from occuring in this code?

key: value:

4. In one or two sentences, explain your reasoning.

 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 5. [5 marks]
Consider the following Stack implementation, which uses an internal Queue (as defined on the Aid Sheet) to
store its data. Complete the push and pop methods. Do not add code anywhere else.
Hint: for one or both methods below, you may need to create a temporary second Stack or Queue.

class Stack:
"""A last-in-first-out (LIFO) stack of items.
"""
# === Private attributes ===
# _items: The items stored in this stack. The FRONT of the _items Queue
# represents the top of this stack.
_items: Queue

def __init__(self) -> None:

"""Initialize a new stack with no items."""
self._items = Queue()

def pop(self) -> Any:

"""Remove and return the item at the top of this Stack.
Precondition: This stack is not empty.
"""

def push(self, item: Any) -> None:

"""Add the given item to the top of this Stack."""
April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 6. [10 marks]

Consider the problem of deleting all occurrences of an item from a LinkedList as defined on the Aid Sheet.
Assume that __contains__ and remove are implemented sensibly.
1. Complete the following function.
def remove_all(lst: LinkedList, v: Any) -> None:
"""Remove all occurences of <v> from <lst>.
>>> lst = LinkedList([2, 1, 3, 1, 4, 1])
>>> remove_all(lst, 1)
>>> print(lst)
[2 -> 3 -> 4]
"""

2. What is the Big-Oh runtime of your function, given a lst of length n where every value is v:
3. Complete the following LinkedList method. You must not make any method or function calls. For
example, your implementation must not call the LinkedList.remove method.
def remove_all(self, v: Any) -> None:
"""Remove all occurences of <v> from this linked list.
>>> lst = LinkedList([2, 1, 3, 1, 4, 1])
>>> lst.remove_all(1)
>>> print(lst)
[2 -> 3 -> 4]
"""

4. What is the Big-Oh runtime of your method on a LinkedList of length n, in the worst case:
 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 7. [6 marks]
Part (a) [2 marks]
Suppose we have a stack of s items, implemented as a linked list with the bottom of the stack at the front of the
linked list and the top of the stack at the end. For each operation, give its big-oh time-complexity, in terms of s.

push

pop

Part (b) [2 marks]

Suppose we have a tree (not necessarily a binary tree) of height h and n nodes. For each operation, give its
big-oh time-complexity in the worst case, in terms of h and/or n.
Write clearly so that we can tell the difference between an h and an n.

determine whether a given item occurs in the tree

determine the height of the tree

Part (c) [1 mark]

Suppose we have a Python list of length n, and we use it to create a new list as follows:

new = []
for item in lst:
new.insert(0, item)

The big-oh time-complexity of this code in terms of n is:

Part (d) [1 mark]

Suppose we have a Python list of length n, and we use it to create a new list as follows:

new = []
for i in range(len(lst) // 2):
new.append(lst[i])

The big-oh time-complexity of this code in terms of n is:

April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 8. [5 marks]
Consider the mystery function below. Complete the four given doctest examples, and write a good, plain English
docstring description for the function explaining its purpose.
You may assume that obj is a nested list, following the definition we have seen in this course. That is, it is
either a single integer or a list of other nested lists. Note that obj has arbitrary depth, and if it is simply an
integer, its depth is 0.

def mystery(obj: Union[int, list], n: int, d: int) -> bool:

"""

>>> mystery(13, 13, _________)

True
>>> mystery(13, 13, _________)
False
>>> mystery([1, [2, [3]]], 3, 3)

>>> mystery([1, [2, [3]]], 1, 3)

"""
if isinstance(obj, int):
return obj == n and d >= 0
else:
for element in obj:
if mystery(element, n, d - 1):
return True
return False
 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 9. [8 marks]
Assume that a Tree class has been defined as described on the Aid Sheet. The following recursive method is to
be added to the class. Complete the method according to its docstring.

def all_strings(self) -> List[str]:

"""Return a list containing all strings that occur along a path in this tree.

A string s occurs along a path in a tree iff s[0] is the value at the root, s[1] is the value
at one of the root’s children, s[2] is the value at one of that node’s children, and so on,
and the last character in s is a leaf. No string occurs in an empty tree.

Precondition: Each value in this tree is a string of length 1.

>>> t = Tree(None, [])

>>> t.all_strings()
[]
>>> t = Tree(‘i’, [Tree(‘t’, []), Tree(‘n’, []), Tree(‘f’, [])])
>>> t.all_strings()
[‘it’, ‘in’, ‘if’]
>>> tiny = Tree (‘r’, [Tree(‘t’, [])])
>>> child1 = Tree(‘a’, [tiny, Tree(‘t’, []), Tree(‘d’, [])])
>>> child2 = Tree(‘r’, [Tree(‘a’, [Tree(‘m’, [])])])
>>> child3 = Tree(‘i’, [])
>>> t = Tree(’p’, [child1, child2, child3])
>>> t.all_strings()
[‘part’, ‘pat’, ‘pad’, ‘pram’, ‘pi’]
"""
April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 10. [5 marks]

Part (a) [1 mark]
Suppose we run the original partition procedure (which returns two lists) that we discussed in lecture, on the
list [6, 1, 8, 5, 1, 2, 9] with 7 as the pivot. What two lists will it return?

Part (b) [2 marks]

Consider the following pairs of lists:

A. [2, 4, 6, 8] and [1, 3, 5, 9]

B. [2, 4, 16, 18] and [19, 27, 28, 33]

Which pair of lists would require fewer comparisons to merge (using the merge algorithm from mergesort)?

Circle one: A B Neither (they both require the same)

Explain your choice. No explanation = no marks.

Part (c) [2 marks]

If I run a sorting algorithm on a list of elements that is already sorted, which of the following algorithms would
be more efficient? Assume that quicksort always chooses the first element as pivot.

Circle one: Quicksort Mergesort Neither (they are equally efficient)

Explain your choice. No explanation = no marks.

 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Question 11. [11 marks]

Part (a) [4 marks] Complete the following BinarySearchTree method according to its docstring. (See the
Aid Sheet for an outline of the class.) You must not create any new instances of BinarySearchTree.

def increase_all_by_x(self, x: int) -> None:

"""Mutate this BST, so that each value is increased by <x>. The mutation
must be done in such a way that the BST property is NEVER violated ---
even temporarily during execution of the method or any recursive calls.

Precondition: x > 0, and all values in this BST are ints.

>>> bst = BinarySearchTree(2)

>>> bst.insert(1)
>>> bst.insert(3)
>>> bst.increase_all_by_x(4)
>>> print(bst)
6
5
7
<BLANKLINE>
"""

Part (b) [1 mark] Consider the problem of constructing a binary search tree of height h > 0, such that it
contains the numbers 1, 2, . . . , 2h − 1. Here are a couple of examples of such binary search trees:

h=2 h=3

Given h, provide a mathematical expression for the value that must go at the root of the tree:
April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Part (c) [6 marks] Complete the following function according to its docstring, without calling insert.
Note that ** is the exponentiation operator in Python. E.g., 2 ** h is 2h .
Hint 1: How is each value in the right subtree related to the the corresponding value in the left subtree?
Hint 2: You should find the method increase_all_by_x helpful. You may use it even if you didn’t complete it.
Hint 3: When creating a new BinarySearchTree, the initializer lets you optionally specify the root’s children.

def construct_tree(h: int) -> BinarySearchTree:

"""Return a BST that contains the integers from 1, 2, ..., (2 ** h) - 1 and has height <h>.

Precondition: h > 0.

>>> c = construct_tree(1)
>>> print(c)
1
<BLANKLINE>
>>> print(construct_tree(2))
2
1
3
<BLANKLINE>
"""
 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Use this page for rough work.

If you want the work on this page to be marked, indicate this clearly at the location of the original question.
April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Use this page for rough work.

If you want the work on this page to be marked, indicate this clearly at the location of the original question.
 April 2022 Examinations
CSC 148 H1S
Duration: 3 hours

Use this page for rough work.

If you want the work on this page to be marked, indicate this clearly at the location of the original question.

End of Exam; Total Marks = 76