Faculty of Arts & Science
December 2019 Examinations
CSC 108 H1F
Question 1. [4 marks]
Part (a) [1 mark] Complete the function is_eligible_for_award according to its docstring below.
def is_eligible_for_award(gpa: float, major: str, req_gpa: float, req_major: str) -> bool:
"""Return True if and only if gpa is greater than or equal to req_gpa and
major is equal to req_major.
>>> is_eligible_for_award(4.0, ‘CS’, 3.5, ‘CS’)
True
>>> is_eligible_for_award(4.0, ‘Econ’, 3.5, ‘CS’)
False
>>> is_eligible_for_award(3.3, ‘CS’, 3.5, ‘CS’)
False
"""
return
Part (b) [3 marks] Complete the function get_award_winners according to its docstring below. Your code must call the function is_eligible_for_award from Part (A).
def get_award_winners(applicants: List[Tuple[float, str, str]], req_gpa: float,
req_major: str) -> List[Tuple[float, str]]:
"""Return a new list of students from applicants who are eligible for an
award, based on req_gpa and req_major. Each student in applicants is of
the form. (gpa, name, major).
In the new list, award winning students should be of the form. (gpa, name)
and should appear in the same order as they appear in the original list.
>>> get_award_winners([(3.6, ‘JC’, ‘CS’), (4.0, ‘MB’, ‘CS’), (3.7, ‘JW’, ‘Econ’)], 3.2, ‘CS’)
[(3.6, ‘JC’), (4.0, ‘MB’)]
>>> get_award_winners([(3.6, ‘JC’, ‘Bio’), (4.0, ‘MB’, ‘Bio’),
(3.7, ‘JW’, ‘Econ’)], 3.7, ‘Bio’)
[(4.0, ‘MB’)]
"""
Question 2. [4 marks]
Function mask_string has been correctly implemented. Fill in the missing parts of the docstring description and examples so that they match the function’s header and body.
def mask_string(s: str, mask: List[bool], ch: str) -> str:
"""Return a new string that is the same as
but with each character that corresponds to a True element in
replaced with .
Precondition : len(ch) == 1 and
>>> mask_string(‘mask’,[True, True, True, True],‘?’)
>>> mask_string(‘ComSc’, [ , , , , ], )
‘C--S-’
"""
masked_string = ‘’
for i in range(len(s)):
if mask[i]:
masked_string = masked_string + ch
else:
masked_string = masked_string + s[i]
return masked_string
Question 3. [6 marks]
In Assignment 1, we split a message into substrings (called tweets), where each tweet had a length equal to MAX_LENGTH characters, except the last tweet which had a length of at least 1 up to MAX_LENGTH (inclusive). For example, for a MAX_LENGTH of 10 and the message ‘This is such an amazing note!’, in A1 we split the message into 3 tweets: ‘This is su’, ‘ch an amaz’, and ‘ing note!’.
You must implement an improved version in which the message is split so that no word is divided across multiple tweets. In this improved version, the message above is split into the 4 tweets with lengths as close to MAX_LENGTH as possible (but not longer than MAX_LENGTH) and spaces omitted from the beginning and end of tweets: ‘This is’, ‘such an’, ‘amazing’, ‘note!’.
Complete the function split_message according to the description above and docstring below. Do not add any code outside of the boxes. Your code must use the provided constant. You may assume that there is exactly one space between words in the message and that there is no whitespace at the beginning or end of the message.
MAX_LENGTH = 10
def split_message(msg: str) -> List[str]:
"""Return a new list containing msg split into tweets so that no words are
divided across multiple tweets. A word is a sequence of non-whitespace
characters. In the tweets, each pair of words must have a space between them.
There should not be any spaces at the beginning or end of tweets.
Precondition: no word in msg is longer than MAX_LENGTH
>>> split_message(‘One hundred and one’)
[‘One’, ‘hundred’, ‘and one’]
"""
# split message into words
tweets =
i=0
while i < :
# combine tweet i and tweet i+1 into a potential tweet
potl_tweet =
if :
# update tweet i to be potential tweet; remove tweet i + 1
else:
# couldn’t combine tweets, so increment i (tweet i is finalized)
i=i+1
return tweets
Question 4. [6 marks]
This problem involves using a point system to score words. Each letter has a point value and is represented in a "letter to points" dictionary, where each key is a lowercase letter and each value is the points corresponding to that letter. An example of a "letter to points" dictionary is:
{‘a’: 1, ‘b’: 2, ‘c’: 3, ‘d’: 2, ‘e’: 1, ‘f’: 4, ..., ‘z’: 10}
Words are scored by adding up the points associated with each of their letters. According to the dictionary above, the word ‘Bee’ is worth 4 points (2 + 1 + 1) and the word ‘bEAd’ is worth 6 points (2 + 1 + 1 + 2). Only lowercase letters appear in "letter to points", so uppercase letters are scored based on the corresponding lowercase letter’s points.
Consider this example ! le with one word per line:
a
BE
bee
Bee
bEAd
Each line in the ! le contains a unique word composed only of letters. Each word has at least one letter. There are no blank lines in the ! le. Words are case-sensitive (e.g., ‘bee’ and ‘Bee’ are considered to be di" erent words.)
Given the example ! le above opened for reading and the "letter to points" dictionary above, function build_word_to_score should return this "word to score" dictionary:
{‘a’: 1, ‘BE’: 3, ‘bee’: 4, ‘Bee’: 4, ‘bEAd’: 6}
Complete the function build_word_to_score according to the example above and the docstring below. You may assume the given ! le has the correct format and the "letter to points" dictionary contains all 26 lowercase letters.
def build_word_to_score(word_file: TextIO, letter_to_points: Dict[str, int]) -> Dict[str, int]:
"""Return a "word to score" dictionary, where each key is a word from word_file and
each value is the score for that word based on the points in letter_to_points.
"""
Question 5. [7 marks]
In this question, you will implement two di" erent algorithms for solving the same problem. Given a list of integers in which each item occurs either once or twice, count the number of items that occur twice.
Part (a) [4 marks]
Complete this function according to its docstring by implementing the algorithm below:
1. Use an integer accumulator to keep track of the number of matches.
2. For each item in lst, compare it to all other items in lst and if the item matches an item other than itself, add to the number of matches.
3. Return the number of duplicates.
Note: you must not use any list methods, but you may use the built-in function len().
To earn marks for this question, you must follow the algorithm described above.
def count_duplicates_v1(lst: List[int]) -> int:
"""Return the number of duplicates in lst.
Precondition: each item in lst occurs either once or twice.
>>> count_duplicates_v1([1, 2, 3, 4])
0
>>> count_duplicates_v1([2, 4, 3, 3, 1, 4])
2
"""
Part (b) [3 marks]
Complete this function according to its docstring by implementing the algorithm below:
1. Use a dictionary accumulator to track items and the number of times they occur in lst.
2. For each item in lst, if it is not already a key in the dictionary, add it along with a value of 1. If it is already a key in the dictionary, increase the value associated with it by 1.
3. Return the di" erence between the number of items in lst and the number of items in the dictionary.
Note: you must not use any list methods, but you may use the built-in function len().
To earn marks for this question, you must follow the algorithm described above.
def count_duplicates_v2(lst: List[int]) -> int:
"""Return the number of duplicates in lst.
Precondition: each item in lst occurs either once or twice.
>>> count_duplicates_v2([1, 2, 3, 4])
0
>>> count_duplicates_v2([2, 4, 3, 3, 1, 4])
2
"""
Question 6. [4 marks]
Part (a) [3 marks] Consider using a List[List[int]] to represent a square grid of integers (as we did in A2 to represent an elevation map). Complete the function swap_rows_and_columns according to its docstring below.
def swap_rows_and_columns(grid: List[List[int]]) -> None:
"""Modify grid so that each row in grid is swapped with the corresponding column.
For example, row 0 is swapped with column 0, row 1 is swapped with column 1, and so on.
Precondition: each list in grid has the same length as grid and len(grid) >= 2
>>> G2 = [[1, 2],
... [3, 4]]
>>> swap_rows_and_columns(G2)
>>> G2 == [[1, 3],
... [2, 4]]
True
>>> G3 = [[1, 2, 3],
... [4, 5, 6],
... [7, 8, 9]]
>>> swap_rows_and_columns(G3)
>>> G3 == [[1, 4, 7],
... [2, 5, 8],
... [3, 6, 9]]
True
"""
Part (b) [1 mark] Circle the term below that best describes the running time of the swap_rows_and_columns function.
constant linear quadratic something else
Question 7. [6 marks]
For this question, a "person to friends" dictionary (Dict[str, List[str]]) has a person’s name as a key and a list of that person’s friends as the corresponding value. You can assume that each person has at least one friend.
Complete the function complete_person_to_friends according to its docstring below. Do not modify the provided code and only write your code after the provided code.
def complete_person_to_friends(p2f: Dict[str, List[str]]) -> None:
"""Modify the "person to friends" dictionary p2f so that all friendships are
bidirectional. That is, if person B is in person A’s list of friends, then
person A must be in person B’s list of friends. The friend lists must be
sorted in alphabetical order.
>>> friend_map = {‘JC’: [‘MB’]}
>>> complete_person_to_friends(friend_map)
>>> friend_map == {‘JC’: [‘MB’], ‘MB’: [‘JC’]}
True
>>> friend_map = {‘B’: [‘A’, ‘D’], ‘A’: [‘B’, ‘C’, ‘D’]}
>>> complete_person_to_friends(friend_map)
>>> friend_map == {‘B’: [‘A’, ‘D’], ‘A’: [‘B’, ‘C’, ‘D’], \
‘D’: [‘A’, ‘B’], ‘C’: [‘A’]}
True
>>> friend_map = {‘JC’: [‘MB’], ‘MB’: [‘JW’]}
>>> friend_map == {‘JC:’: [‘MB’], ‘MB’: [‘JC’, ‘JW’], ‘JW’: [‘MB’]}
>>> complete_person_to_friends(friend_map)
True
"""
keys = list(p2f.keys())
for person in keys:
Question 8. [7 marks]
Consider the function below:
def get_first_even(items: List[int]) -> int:
"""Return the first even number from items. Return -1 if items contains
no even numbers. The number 0 is considered to be even.
"""
Part (a) [5 marks] Add ! ve more distinct test cases to the table below. Do not test if the input, items, is mutated. No marks will be given for duplicated test cases. The six test cases below are not intended to be a complete test suite.
Test Case Description items Expected Return Value
The empty list [] -1
Part (b) [2 marks] A buggy implementation of the get_first_even function is shown below. In the table below, complete the two test cases by ! lling in the three elements of items. The ! rst test case should not indicate a bug in the function (the test case would pass), while the second test case should indicate a bug (the test case would fail). Both test cases should pass on a correct implementation of the function. If appropriate, you may use test(s) from Part (a).
def get_first_even(items: List[int]) -> int:
even_number = -1
for item in items:
if item % 2 == 0:
even_number = item
return even_number
items Expected Return Value Actual Return Value
Does not indicate bug (pass) [,,]
Indicates bug (fail) [,,]