DECEMBER 2017 EXAMINATIONS
CSC 108 H1F
Question 1. [6 marks]
Each of the following sets of Python statements will result in an error when the code is run. In the table below, briefly explain why each error occurs.
Python statements Briefly explain why each error occurs
stations = ('Pape', 'King', 'Kipling')
stations[0] = 'St. George'
st_to_line = {'Chester': 2,
'Davisville': 1,
'Union': 1}
if st_to_line['Dundas'] == 1:
print('Yonge-University')
i=0
lines = [1, 2, 3, 4]
while lines[i] != 5 and i < len(lines):
print(lines[i])
i=i+1
stops = ['Christie', 'Bay', 'Spadina']
sorted_stops = stops.sort()
reversed_stops = sorted_stops.reverse()
station = 'Sheppard West'
station[-4] = 'E'
station[-3] = 'a'
# Assume the next line runs without error.
f = open('stations.txt')
f.read()
f.readline()[0]
Question 2. [4 marks]
Fill in the boxes with the while loop condition and the while loop body required for the function to work as described in its docstring. See the bottom of this page for examples.
def get_and_verify_password(password: str) -> bool:
"""Repeatedly prompt the user to enter their password until they get it
correct or until they guess wrong three times. Return True if and only if
the password was entered correctly.
"""
msg = 'Enter your password: '
guess = input(msg)
num_guesses = 1
while :
return guess == password
Here are examples from using a correct implementation of get_and_verify_password:
>>> get_and_verify_password('csc108!')
Enter your password: csc108!
True
>>>
>>> get_and_verify_password('^S33kReT')
Enter your password: chairman
Enter your password: ^S33kReT
True
>>>
>>> get_and_verify_password('csc108!')
Enter your password: CSC
Enter your password: 108
Enter your password: IDoNotKnow
False
>>>
Question 3. [6 marks]
In this question, you are to write code that uses a Python dictionary where each key represents the name of a meal (e.g., 'stew', 'eggs') and the associated value represents a list of table numbers (e.g., 1, 2, 3), with one list item for each meal order. If there are, for example, three orders for 'stew' at table 2, then 2 will appear three times in the list of table numbers associated with 'stew'.
Part (a) [3 marks] Complete the following function according to its docstring.
def get_num_orders(meal_to_tables: Dict[str, List[int]], meal: str) -> int:
"""Return the number of orders for meal in meal_to_tables.
>>> m_to_t = {'stew': [4, 1], 'eggs': [6]}
>>> get_num_orders(m_to_t, 'stew')
2
>>> get_num_orders(m_to_t, 'eggs')
1
>>> get_num_orders(m_to_t, 'brussel sprouts')
0
"""
Part (b) [3 marks] Complete the following function according to its docstring.
def order_meal(meal_to_tables: Dict[str, List[int]], meal: str, table: int) -> None:
"""Modify meal_to_tables to include a new order for meal at table. Place
table at the end of the list of table number(s) associated with meal.
>>> m_to_t = {}
>>> order_meal(m_to_t, 'stew', 4)
>>> m_to_t == {'stew': [4]}
True
>>> order_meal(m_to_t, 'stew', 1)
>>> m_to_t == {'stew': [4, 1]}
True
>>> order_meal(m_to_t, 'eggs', 6)
>>> m_to_t == {'stew': [4, 1], 'eggs': [6]}
True
"""
Question 4. [4 marks]
Complete the following function according to its docstring.
def char_count(s: str, words: List[str]) -> List[int]:
"""Return a new list in which each item is the number of times
that the character at the corresponding position of s appears in
the string at the corresponding position of words.
Lowercase and uppercase characters are considered different.
Precondition: len(s) == len(words)
# In the example below, 'a' is in 'apple' 1 time,
# 'n' is in 'banana' 2 times, and
# 'b' is in 'orange' 0 times.
>>> char_count('anb', ['apple', 'banana', 'orange'])
[1, 2, 0]
>>> char_count('xdaao', ['cat', 'dog', 'cat', 'banana', 'cool'])
[0, 1, 1, 3, 2]
>>> char_count('fW', ['sandwiches', 'waffles'])
[0, 0]
"""
Question 5. [4 marks]
The docstring below is correct. However, the code in the function body contains one or more bugs. As a result the function does not work as specified in the docstring.
def increment_sublist(L: List[int], start: int, end: int) -> None:
"""Modify L so that each element whose index is in the range from start (inclusive)
to end (exclusive) is incremented by 1.
Precondition: 0 <= start < end <= len(L)
>>> a_list = [10, 20, 30, 40, 50, 60]
>>> increment_sublist(a_list, 0, 3)
>>> a_list
[11, 21, 31, 40, 50, 60]
"""
for value in L[start:end]:
value = value + 1
Part (a) [1 mark]
Complete the example below to show what happens when the buggy function body given above is used.
>>> a_list = [10, 20, 30, 40, 50, 60]
>>> increment_sublist(a_list, 0, 3)
>>> a_list
Part (b) [3 marks]
Write a new function body that correctly implements the function as described in its docstring above.
def increment_sublist(L: List[int], start: int, end: int) -> None:
"""
"""
Question 6. [6 marks]
In each of the following, circle the best answer that follows directly below the question.
Part (a) [1 mark] If you were searching a sorted list of one million unique items for a particular value, and the value being searched for was the second item in the sorted list, which algorithm would take the least time?
linear binary a tie between linear an error
search search search and binary search would occur
Part (b) [1 mark] If you were searching a sorted list of one million unique items for a particular value, and the value being searched for was not in the sorted list, which algorithm would take the least time to discover that it was not in the list?
linear binary a tie between linear an error
search search search and binary search would occur
Part (c) [1 mark] If you had an unsorted list of one million unique items, and knew that you would only search it once for a value, which of the following algorithms would be the fastest?
use linear use insertion sort use insertion sort an error
search on the to sort the list to sort the list would occur
unsorted list and then binary and then linear
search on the search on the
sorted list sorted list
Part (d) [1 mark] Our sorting code completes all passes of the algorithm, even if the list becomes sorted before the last pass. After how many passes of the bubble sort algorithm on the list [ 3, 1, 6, 4, 9, 8 ] could we stop because the list has become sorted?
1 3 5 7
Part (e) [1 mark]Our sorting code completes all passes of the algorithm, even if the list becomes sorted be-fore the last pass. After how many passes of the insertion sort algorithm on the list [ 9, 8, 3, 1, 6, 4 ] could we stop because the list has become sorted?
1 2 6 9
Part (f) [1 mark]Our sorting code completes all passes of the algorithm, even if the list becomes sorted be-fore the last pass. After how many passes of the selection sort algorithm on the list [ 9, 8, 6, 4, 3, 1 ] could we stop because the list has become sorted?
1 3 5 7
Question 7. [6 marks]
Complete the following function according to its docstring.
Your code must not mutate the parameters!
def collect_sublists(L: List[List[int]], threshold: int) -> List[List[int]]:
"""Return a new list containing the sublists of L in which all the values
in the sublist are above threshold.
Precondition: all sublists of L have length >= 1
>>> collect_sublists([[1, 2, 3], [4, 5, 6], [7, 8, 9]], 5)
[[7, 8, 9]]
>>> collect_sublists([[15, 20], [10, 11], [30, 40], [7, 17]], 10)
[[15, 20], [30, 40]]
"""
Question 8. [3 marks]
Fill in the boxes to complete the docstring examples for the function below.
def mystery(L: List[str], D: Dict[str, str]) -> None:
"""
>>> list1 = ['I', 'love', 'midterms']
>>> dict1 = {'midterms': 'finals'}
>>> mystery(list1, dict1)
>>> list1
>>> dict2 =
>>> mystery(list1, dict2)
>>> list1
['We', 'love', 'programming']
>>> list3 = ['m', 'y', 'q', 'p', 'w', 'm']
>>> dict3 = {'m': 'r', 'q': 'r'}
>>> mystery(list3, dict3)
>>> list3
"""
for key in D:
index = L.index(key)
L[index] = D[key]
Question 9. [5 marks]
Part (a) [4 marks] The docstring below is correct. However, the code in the function body contains one or more bugs. As a result the function does not work as specified in the docstring.
def is_valid_word(potential_word: str, word_list: List[str]) -> bool:
"""Return True if and only if potential_word is one of the items in word_list.
>>> is_valid_word('cat', ['cat', 'dog', 'fox'])
True
>>> is_valid_word('wombat', ['cat', 'dog', 'fox'])
False
"""
for word in word_list:
if potential_word in word:
return True
else:
return False
Complete the unittest code below so that: (1) the assertions both fail when the buggy function body given above is used, and (2) the assertions both pass when a function body that correctly implements the function as described in its docstring is used. Both arguments must have the correct type. Assume that the is_valid_word function has been correctly imported and may be called as written below.
class TestIsValidWord(unittest.TestCase):
def test_case1(self):
potential_word =
word_list =
actual = is_valid_word(potential_word, word_list)
expected = False
self.assertEqual(actual, expected)
def test_case2(self):
potential_word =
word_list =
actual = is_valid_word(potential_word, word_list)
expected = True
self.assertEqual(actual, expected)
Part (b) [1 mark] Circle the term below that best describes the number of times the loop iterates when the buggy version of the is_valid_word function given in Part (a) is called.
constant linear quadratic something else
Question 10. [6 marks]
Consider this code:
def mystery(n: int) -> None:
"""
"""
for i in range(n):
for j in range(n):
if i == j:
print(i + j)
Part (a) [1 mark]
What is printed when mystery(3) is executed?
Part (b) [1 mark]
Write an English description of what function mystery prints in terms of n.
Part (c) [1 mark]
For function mystery the best and worst case running times are the same. Circle the term below that best describes the running time of the mystery function as written above.
constant linear quadratic something else
Part (d) [2 marks]
The code above can be rewritten to complete the same task, but with a reduced running time. Write the body of a new version of mystery in which the running time expressed in terms of n is improved.
def mystery_improved(n: int) -> None:
"""
"""
Part (e) [1 mark]
Circle the term below that best describes the running time of the your mystery_improved function.
constant linear quadratic something else
Question 11. [12 marks]
Part (a) [6 marks]
Station data is stored in a comma separated values (CSV) file with one station’s ID, name, latitude, and longitude per line in that order. Here is an example station data CSV file:
1,Allen,43.667158,-79.4028
12,Bayview,43.656518,-79.389
8,Chester,43.648093,-79.384749
17,Davisville,43.66009,-79.385653
Given the example station data CSV file opened for reading, function build_dictionaries returns:
({1: [43.667158, -79.4028], 12: [43.656518, -79.389],
8: [43.648093, -79.384749], 17: [43.66009, -79.385653]},
{1: 'Allen', 12: 'Bayview', 8: 'Chester', 17: 'Davisville'})
Complete the function build_dictionaries according to the example above and its docstring below.
Assume the given file has the correct format.
def build_dictionaries(f: TextIO) -> Tuple[Dict[int, List[float]], Dict[int, str]]:
"""Return a tuple of two dictionaries with station data from f. The first dictionary
has station IDs as keys and station locations (two item lists with latitude and longitude)
as values. The second dictionary has station IDs as keys and station names as values.
Precondition: station IDs in f are unique
"""
Part (b) [6 marks]
You may assume the function get_distance has been implemented:
def get_distance(lat1: float, long1: float, lat2: float, long2: float) -> float:
"""Return the distance between the location at lat1 and long1 and
the location at lat2 and long2.
"""
Using get_distance as a helper function, complete function get_closest_station according to its docstring:
def get_closest_station(lat: float, long: float, id_to_location: Dict[int, List[float]],
id_to_name: Dict[int, str]) -> str:
"""Return the name of the station in id_to_name and id_to_location that is
closest to latitude lat and longitude long. You may assume that exactly one
station is closest.
Precondition: id_to_location and id_to_name have the same keys
and len(id_to_location) >= 1
>>> id_to_location = {3: [40.8, -73.97], 4: [43.6, -79.4], 11: [51.5, -0.1]}
>>> id_to_name = {3: 'Grand Central', 4: 'Union', 11: 'Blackfriars'}
>>> get_closest_station(43.5, -79.6, id_to_location, id_to_name)
'Union'
"""