CSC110Y1F (All Sections)
Final Examination
Date: December 2022 Examination Period
1. [15 marks] Short answer.
(a) [3 marks] Each of the following interactions in the Python console ends with an expression and blank space. For each one, write the value that would be displayed. If evaluating the code would cause an error,
write “ERROR” and briefly explain why the error would occur.
>>> len('CSC110') + len({'abc'})
>>> {'hi': 2, 'bye': 3}[2]
>>> sum([x * 2 for x in [1, 3, 5] if x > 2])
>>> words = ['chocolate', 'orange', 'is', 'tasty']
>>> words[1][0] + words[0][1] + words[3][0]
>>> my_stack = Stack1() # Assume this is a valid Stack implementation
>>> my_stack.push(1)
>>> my_stack.push(2)
>>> my_stack.pop()
>>> numbers = [10, 1, 3]
>>> numbers = list.sort(numbers)
>>> numbers[0]
(b) [5 marks] Answer each of the following questions. You only need 1-3 sentences per response.
(i) David says, “The Python interpreter allows us to access private instance attributes of a class, so it’s useless to mark instance attributes as private.” Explain why David is incorrect.
(ii) Tom says, “The Diffie-Hellman algorithm is an example of a symmetric-key cryptosystem.” Explain why Tom is incorrect.
(iii) Define the term abstract method.
(iv) In our Python files, we typically write testing code like doctest.testmod() inside an if statement, if name == ‘ main ’ . Explain why we do this.
(v) In our run simulation function, we used a priority queue (events) to store the simulation’s events. For your reference, here is the main simulation loop code:
while not events .is_empty():
event = events.dequeue()
new_events = event.handle_event(system)
for new_event in new_events:
events.enqueue(new_event)
Explain why we used a priority queue instead of a queue.
(c) [3 marks] Consider the following code:
@dataclass
class Person:
"""A person .
Instance Attributes:
- name: The name of this person .
- pet: A pet dog that this person owns, or None if this person does not own a pet dog .
"""
name: str
pet: Optional[Dog] = None
@dataclass
class Dog:
"""A pet dog .
Instance Attributes:
- name: The name of this dog .
- owner: The person who owns this dog .
"""
name: str
owner: Person
(i) What does the type annotation Optional[Dog] (for pet) mean?
(ii) Translate the following Person representation invariant into valid Python code: “If this person (self) owns a pet dog, then that dog’s owner is the same object as self.”
(d) [4 marks] Consider the following function definition, which uses the defintions from the previous part.
def get_dog(person: Person, dog_name: str) -> Dog:
"""Modify the given person to become the owner of a new dog named dog_name . Return the new dog .
Preconditions:
- person.pet is None
"""
# MARKER A
new_dog = Dog(name=dog_name, owner=person) person.pet = new_dog
# MARKER B
return new_dog
Suppose we run this function in the Python console and execute the following code:
>>> tom = Person(name='Tom') >>> get_dog(tom, 'Fluffy')
The object-based memory model diagram below shows the state of memory at MARKER A, when get dog is first called.
Modify the diagram to show the the state of memory at MARKER B, immediately before get dog returns. You may need to add additional boxes for new objects, and/or modify existing parts of the diagram.
2. [9 marks] Programming.
(a) [4 marks] Implement the following function, according to its docstring. You must use comprehension expressions in your solution, and may not use loops.
You may, but are not required to, define a helper function in your solution. Any helper functions you define must include type annotations but do not need to include a docstring.
def len_special_lists(lists_of_numbers: list[list[int]]) -> list[int]: """Return the lengths of the given lists of numbers that contain
at least one even integer .
>>> lists1 = [[1, 3], [110], [1, 2, 3, 4]]
>>> len_special_lists(lists1) # [110] and [1, 2, 3, 4] have at least one even integer [1, 4]
>>> lists2 = [[], [1], [1, 3, 5, 7]]
>>> len_special_lists(lists2) # No list has at least one even integer []
"""
# TODO: write your function body here
(b) [5 marks] This part considers a function nutrient totals with two parameters:
• foods: set[str]. A set of foods in a meal, for example: {'twinkie', 'fries'}
• food to nutrients: dict[str, dict[str, int]]. A nested dict that stores the number of grams of ‘carbs’ , ‘protein’, and ‘fat’ in different food items. For example:
{'twinkie': {'carbs': 47, 'protein': 2, 'fat': 9 }, 'fries': {'carbs': 40, 'protein': 3, 'fat': 17}, 'protein bar': {'carbs': 21, 'protein': 20, 'fat': 5 }}
nutrient totals returns a new dict containing the total number of grams of ‘carbs’ , ‘protein’, and ‘fat’ across all of the given foods.
Complete function nutrient totals by implementing the function body. You may not define any helper functions.
def nutrient_totals(foods: set[str],
food_to_nutrients: dict[str, dict[str, int]]) -> dict[str, int]: """See description above .
Preconditions:
- all(food in food_to_nutrients for food in foods)
- food_to_nutrients is in the format described above
>>> f_to_n = {'twinkie': {'carbs': 47, 'protein': 2, 'fat': 9 }, . . . 'fries': {'carbs': 40, 'protein': 3, 'fat': 17}, . . . 'protein bar': {'carbs': 21, 'protein': 20, 'fat': 5 }} >>> actual = nutrient_totals({'twinkie', 'fries'}, f_to_n)
>>> expected = {'carbs': 47 + 40, 'protein': 2 + 3, 'fat': 9 + 17} >>> actual == expected
True """
# Accumulate the result in the following provided dict nutrients_so_far = {'carbs': 0, 'protein': 0, 'fat': 0}
# TODO: complete the body of the function
return nutrients_so_far
3. [5 marks] Debugging and testing.
Consider the following function definition.
def space_counts(strings: list[str]) -> list[int]:
"""Return the number of space characters in each given string .
>>> space_counts(['Tom', 'David is cool']) [0, 2]
"""
spaces_so_far = 0 counts_so_far = []
for string in strings: for char in string:
if char == ' ': # Check whether char is a space spaces_so_far += 1
list.append(counts_so_far, spaces_so_far) return counts_so_far
This implementation of space counts does pass the doctest example, but actually has a subtle error, and so is not correct on all possible inputs to the function.
(a) [2 marks] Complete the unit test below to show an example valid input to space counts that will cause the test to fail because this implementation returns an incorrect value.
def test_space_counts_error() -> None:
"""A test case for space_counts that reveals an error in the given implementation .
If we ran this test with pytest and the current implementation, we would expect this test to *fail* because of the error in the function body .
"""
actual = space_counts( ) # FILL THIS IN
expected = # FILL THIS IN
assert actual == expected
(b) [1 mark] Explain what is the error in the given implementation. Do not explain how to fix the error here.
(c) [1 mark] Explain how to fix the error.
(d) [1 mark] Explain why the doctest example passes for the given implementation of space counts, even though that implementation has an error. For your reference, here is the doctest example:
>>> space_counts(['Tom', 'David is cool']) [0, 2]
4. [6 marks] Number theory. Consider the following statement:
“For all integers a, b, and c, IF gcd(a,b) = 1 and a divides bc, THEN a divides c.”
(a) [1 mark] Translate the above statement into symbolic logic. You may use the gcd function and divisibility symbol | in your translation; do not expand the definition of divisibility.
(b) [5 marks] Prove the above statement.
Your proof may use any definitions and theorems provided on the Reference Sheets, but no other theo- rems/properties of divisibility or modular equivalence. We have left space for rough work here and on the next page, but please write your formal proof in the box below.
Hint: use the GCD Characterization Theorem and multiply an equation by c.
5. [9 marks] Object-Oriented Modelling.
In this question, you will write Python code to model students and courses at a university.
(a) [5 marks] First you’ll create a data class to represent a student, based on the following description:
A student has a user name (e.g., ‘liudavid’) and a mapping to keep track of courses they have passed, where each key of the mapping is a course code (e.g., ‘CSC110’) and the associated value is the integer grade they received in that course (e.g., 85).
Each student must satisfy the following properties:
1. The student’s user name is non-empty.
2. Every grade associated with a passed course is between 50 and 100, inclusive.
In the space below, complete the data class by writing instance attribute names and type annotations in the class body and appropriate representation invariants in the docstring.
NOTE: You may not use the dict .values method in this question.
@dataclass
class Student:
"""A class representing a university student .
NOTE: you do not need to write English descriptions of the instance attributes . Just make sure to pick meaningful attribute names in the class body .
Representation Invariants: (TODO: write appropriate representation invariants here)
"""
# TODO: write appropriate instance attribute names and type annotations here
(b) [4 marks] In the space below, we’ve begun a class Course to represent a university course.
class Course:
"""A class representing a university course .
Instance Attributes:
- code: This course's course code, e.g . 'CSC110'
- students: A list of students currently enrolled in this course
Representation Invariants:
- every student in self .students has a unique user name
"""
code: str
students: list[Student]
Complete the following method for the Course class. You may not define any helper functions.
class Course:
. . . # continued from above
def enrol(self, student: Student) -> bool:
"""Enrol the given student in this course and return whether the student was successfully enrolled .
Do NOT enrol the student if either:
1 . The student has already passed this course (i .e . , this course's code is in the student's "passed courses" mapping) .
2 . There is a student with the same user name already enrolled in this course .
(In those two cases, False should be returned.)
"""
6. [6 marks] Running-time analysis.
Analyse the running time of the following function, in terms of n, the length of its input list, and/or the input value m. To simplify your analysis, you may ignore the running time of Line 4.
|
def loopy(numbers: list[int], m: int) -> None:
|
# Line
|
1
|
|
|
"""Precondition: m >= 0"""
|
# Line
|
2
|
|
|
for number in numbers:
|
# Line
|
3 (Loop
|
1)
|
|
i = 1
|
# Line
|
4
|
|
|
while i < m:
|
# Loop
|
5 (Loop
|
2)
|
|
i = i * 3
|
# Loop
|
6
|
|
|
print(i + number)
|
# Loop
|
7
|
|
|
print(sum(numbers))
|
# Loop
|
8
|
|
|
Note: for all lists x, sum(x) takes len(x) steps.
|
|
|
|
7. [7 marks] Worst-case running-time analysis. You are given the following function:
def f(numbers: list[int], m: int) -> None: """Precondition: m >= 0"""
for i in range(0, m): if i in numbers:
print('Found') else:
print('Not found')
(a) [5 marks] Perform. a lower bound analysis of the worst-case running time of this function, in terms of n, the length of numbers, and/or the input value m. The Omega expression that you conclude should be tight, meaning that the worst-case running time should be Theta of this expression, but you are not required to show that.
(b) [2 marks] Suppose we modify f so that the numbers parameter is a set[int] instead of a list[int]. How would the running time of this function change? Briefly explain your answer, but do not perform a formal running-time analysis.
8. [3 marks] Stacks/Queues/Priority Queues ADTs.
|
Warning: this is meant to be a challenging question, and is deliberately weighted less than other questions. We strongly recommend completing the rest of this exam before attempting this question.
|
Implement the following function, according to its docstring. You may not define any helper functions.
def pop_biggest(stacks: list[Stack]) -> int:
"""Remove and return the maximum item that is on the top of one of the given stacks . Return 0 if all given stacks are empty .
Preconditions:
- the top element of each stack is an int and is > 0
- the top element of each stack is unique (so don't worry about ties)
"""
# TODO: write your function body here