CSC 110 Y1F
FINAL EXAMINATION
December 2023
Question 1. Short answer [9 marks]
Assume each of the pieces of code below is being typed into the Python console. Each subquestion (Part (a), Part (b), etc.) is independent of the others, but within each part, each line of code is affected by all the code that is executed before it.
In each space below, write what would be displayed, if anything. If there is any part of the code that would cause an error, write ERROR underneath that piece and briefly explain why that error would happen.
Part (a) [3 marks]
>>> class_list = [[ ' Simran ' , ' A+ '], [ ' Bob ' , ' B- '], [ ' James ' , ' A+ '], [ ' Sadia ' , ' C ']] >>> len(class_list)
>>> len(class_list[0][0])
>>> class_list.pop()
>>> class_list[len(class_list) - 1]
Part (b) [3 marks]
>>> class_dict = { ' A+ ' : [ ' Mia ' , ' Bumbly '], ' B- ' : [' Bob '], ' C ' : [' Sadia ']} >>> class_dict[' Mia ']
>>> class_dict[' A+ '] += class_dict[' C '] >>> class_dict[' C '] = [' Tom ']
>>> class_dict[' A+ '] >>> class_dict[' C ']
Part (c) [3 marks]
>>> fave_colours = [( ' Bob ' , ' Yellow ' ), ( ' Tom ' , ' Green ' ), \
. . . ( ' Sadia ' , ' Pink ' ), ( ' Mia ' , ' Sparkly ' )]
>>> fave_colours[0][0]
>>> fave_colours.append(( ' Ali ' , ' Red ' )) >>> len(fave_colours)
>>> fave_colours[2][1] = ' Rainbow ' >>> fave_colours[2][1]
Question 2. Memory Model [4 marks]
Below is an object-based memory model diagram showing the state of the memory model at the moment immediately before a program ends.
Part (a) [1 mark]
If the last thing the program did was print(things), what would be the output?
Part (b) [3 marks]
Complete the following code so it will generate the memory model diagram shown above by putting an expression or statement in each of the three boxes. Do not add in any extra lines or change anything else.
def binoo(stuff: list, i: int) -> None:
stuff[i] =
def toopy(lst: list, add: str) -> None: binoo(lst[0], 1)
if __name__ == ' __main__ ' : nums = [26, 17, 39]
word = ' hi '
things =
toopy(things, ' ! ' )
Question 3. Tabular data [19 marks]
Consider the tabular data below. It provides information on all of Sadia’s pets. Each sublist has information about a single pet, with the information given in the order: [name, species, age].
pet_data = [
. . . [ ' Kyoko ' , ' cat ' , 14],
. . . [' Chirly ' , ' bird ' , 4],
. . . [' Bumbly ' , ' dog ' , 5],
. . . [ ' Pocoyo ' , ' cat ' , 3],
. . . [ ' Tomoyo ' , ' cat ' , 3],
. . . [ ' Mia ' , ' dog ' , 2]
. . . ]
Complete each of the following questions. They all involve data about pets stored using the format described above. Part (a) [3 marks]
Complete the following function according to its docstring. In your solution, you may not use loops. Use a comprehension. def is_senior(cur_pets: list[list], pet_name: str) -> bool:
"""Return whether the pet with the given pet_name is a senior pet (at least 8 years old) .
The list cur_pets is structured in the same way as in the example pet_data provided at the start of this question .
Preconditions:
- All pet names in cur_pets are unique
- pet_name exists as a pet ' s name in cur_pets
>>> is_senior(pet_data, ' Kyoko ' ) True
>>> is_senior([[ ' Luna ' , ' cat ' , 9], [ ' Belgirl ' , ' cat ' , 3]], ' Belgirl ' )
False """
# Note: You must use comprehensions below . Loops are not allowed .
Part (b) [2 marks]
Complete the following function according to its docstring. In your solution, you may not use loops. Use a comprehension. def get_species(cur_pets: list[list]) -> set[str]:
"""Return a set of all the species in the given cur_pets list of lists .
The list cur_pets is structured in the same way as in the example pet_data provided at the start of this question .
>>> get_species(pet_data) == { ' cat ' , ' dog ' , ' bird '} True
>>> one_pet = [[' Bonny ' , ' dog ' , 3]] >>> get_species(one_pet)
{' dog '}
"""
# Note: You must use comprehensions below . Loops are not allowed . # Complete the function body below according to the docstring .
Part (c) [4 marks]
Complete the following function according to its docstring. In your solution, you may not use loops. You should use either any and/or all, and use one or more of the functions from the previous parts as a helper. You may assume the
functions from Parts (a) and (b) are available to use and are implemented correctly. def all_dogs_and_some_senior(cur_pets: list[list]) -> bool:
"""Return whether all pets in cur_pets are of the species ' dog ' and at least one of them is a senior pet (at least 8 years old) .
>>> some_pets = [[ ' Aisha ' , ' dog ' , 16], [ ' Murphy ' , ' dog ' , 4]] >>> all_dogs_and_some_senior(some_pets)
True """
# Note: You must use any() and/or all(), and one or more of the functions from Part (a) # and/or Part (b) as a helper . Loops are not allowed .
Part (d) [6 marks]
Sadia recently got a raise! So, naturally it might be time to get another pet. Help her figure out what type of pet to get next by completing the function below. The function takes in a list of current pets and also a dictionary that maps various species to an ideal number of that species to have. The function returns a new dictionary that maps each species given in the ideal number dictionary to how many more of that species Sadia needs to reach her ideal number.
def new_pets_needed(cur_pets: list[list], ideal_pet_counts: dict[str, int]) -> dict[str, int]:
"""Return a new dictionary that maps each species from ideal_pet_counts to the number of
new pets of that species that are needed to reach the ideal count . If the current number of that
species owned is already greater than or equal to the ideal number, the number of new pets of that species that are needed should be 0 .
The list cur_pets is structured in the same way as in the example pet_data, and includes information about each pet a person already has .
The dict ideal_pet_counts is a dictionary that maps species to the ideal number of pets of that species that the person wants to have .
Preconditions:
- all([ideal_pet_counts[species] >= 0 for species in ideal_pet_counts])
>>> res = new_pets_needed(pet_data, { ' cat ' : 10, ' tarantula ' : 0, ' dog ' : 1}) >>> res == { ' cat ' : 7, ' tarantula ' : 0, ' dog ' : 0}
True """
Part (e) [2 marks]
Sadia realized it’s almost 2024, and she forgot to update all her pets’ ages this year! Complete the function below to help her add one to each pet’s age in a given pet data list of lists.
def increment_ages(cur_pets: list[list]) -> None:
"""Increment the age of all pets in cur_pets list of lists by one .
The list cur_pets is structured in the same way as in the example pet_data provided at the start of this question .
>>> two_pets = [[ ' Luna ' , ' cat ' , 1], [ ' Lulu ' , ' cat ' , 3]] >>> increment_ages(two_pets)
>>> two_pets
[[ ' Luna ' , ' cat ' , 2], [ ' Lulu ' , ' cat ' , 4]]
"""
Part (f) [2 marks]
Sadia wants to write a bunch of pytest functions to make sure increment_ages is working correctly and she asked her student Bob to help. Bob wrote the pytest method below but it seems to fail even when the increment_ages function appears to be correct.
def test_increment_ages() -> None:
"""Test that increment_ages mutates the list it is given correctly . """
lst = [[ ' Luna ' , ' cat ' , 1]]
result = increment_ages(lst)
assert result == [[ ' Luna ' , ' cat ' , 2]]
What programming error has Bob made when writing his pytest function? Explain clearly below.
Fix Bob’s programming error by writing a correct pytest method for the increment_ages function below: def test_increment_ages() -> None:
"""Test that increment_ages mutates the list it is given correctly . """
Question 4. Dataclasses [6 marks]
Sadia decided to represent her pet data using the below dataclass instead of a list of sublists:
@dataclass
class Pet:
name: str
species: str
birthdate: date # date is imported from the datetime module
Notice that she decided to use an attribute for the pet’s birthday instead of keeping track of it’s age, just in case she forgets to update the age again.
Sadia will instead use the function get_age that takes in an instance of the Pet dataclass and returns the age of the described pet based on today’s date (provided as a date object).
The use of the date object is demonstrated in the following Python console log:
>>> from datetime import date
>>> d = date(2008, 7, 23) # Example date object >>> d.year
2008
>>> d.month 7
>>> d.day 23
Part (a) [2 marks]
Complete the doctest examples below to create an instance of a cat named Pudding born on date(2020, 11, 2) for the first test, and an instance of a dog named Miracle born on date(2022, 12, 25) for the second test.
def get_age(p: Pet, today: date) -> int:
"""Return how old p is in years, based on today ' s date . # Test for cat whose birthday already happened this year >>> cat =
>>> get_age(cat, date(2023, 12, 15)) 3
# Test for dog whose birthday has not yet happened this year >>> dog =
>>> get_age(dog, date(2023, 12, 15)) 0
"""
# Note: the function body will be completed in the next part of this question
Part (b) [4 marks]
Bob wrote some code that correctly completes the function body for get_age so that it returns a given pet’s age in years. A pet is considered to be 0 years old until they reach their first birthday. Bob used the following algorithm for his code:
Subtract the birthday year from today’s year. But, if the birthday has not been celebrated yet this year, subtract one from the difference. Also, if the pet hasn’t even been born yet, simply return 0.
However, Bob somehow corrupted his file and now all his lines of code are out of order! Unscramble the code below by rewriting each line in the right order. Be sure to include proper indentation within your code.
Do NOT add in any additional lines. Use only the lines exactly as provided in the list below.
1. if d.month > today.month or (d.month == today.month and d.day > today.day):
2. years = today.year - d.year
3. d = p.birthdate
4. return 0
5. if d.year < today.year:
6. years -= 1
7. return years
8. else:
def get_age(p: Pet, today: date) -> int:
"""Return how old p is in years, based on today ' s date . """
# Write a correct implementation of Bob ' s algorithm below by unscrambling his lines of code . # Use ONLY and EXACTLY the lines of code provided above, do not add in any new lines .
# Add in proper indentation as needed .
Question 5. Number theory and logic [4 marks] Disprove the following statement:
∀a,b, n ∈ Z+ , (a 三 b (mod n)) ⇒ (a % n = b)
Write your formal disproof of the statement below:
Question 6. Runtime analysis [4 marks]
For both of the functions below, analyze the running time of the function in terms of n (the given value or the length of the given set).
Provide an exact step count (no need to simplify mathematical expressions – e.g. leaving something as 2 * 3 instead of writing 6 is fine). Also provide the associated Θ expression for the running time. (No further explanation for the Θ expression step is required.)
Part (a) [2 marks]
def f1(n: int) -> int:
"""Docstring omitted . """
i = 0 j = 0
while i <= 10:
while j <= 5:
j += 1 i += 1
return i + j
Part (b) [2 marks]
def f2(numbers: set[int]) -> bool: """Docstring omitted . """
return 0 in numbers
Question 7. Worst-case running-time analysis [4 marks]
Consider the following function, which takes as input a list of nonnegative integers.
def f3(numbers: list[int]) -> None:
"""
Preconditions:
- all(numbers[i] >= 0 for i in range(0, len(numbers)))
"""
for i in range(0, len(numbers)): # Loop 1 if numbers[i] % 2 == 0:
for j in range(numbers[i], len(numbers)): # Loop 2 numbers[j] = 1
Note: There are no items in range(a, b) when b <= a.
Perform an upper bound analysis of the worst-case running time of this function, in terms of n, the length of numbers.
Notes:
1. You may go from a step count expression (e.g., 2n + 3) to a final Big-O expression (e.g., O(n)) without proof.
2. Your final Big-O expression must be fully simplified (e.g., O(n3 ) is fully simplified, while O(4n3 + 2n + 3) is not).
3. The Big-O expression that you conclude must be as tight as possible.
4. Use “at most” or ≤ to explicitly indicate where a step count expression is an upper bound.
Question 8. Classes and ADTs [5 marks]
Consider the following Stack3 class, a new concrete implementation of the Stack abstract class, which uses an internal Queue1 object (Queue1 is a concrete implementation of the Queue abstract class) to store its data.
The top of Stack3 will be represented by the front of Queue1. You have access to the Queue’s public interface (as defined in the reference sheet).
Complete the push and pop methods below. Do not add any other methods or modify the given code.
Hints and rules: For one or both of the methods that you write, you may want to create a second type Queue1 object. This is allowed. You are not allowed to create any other types of collection objects (i.e., no new lists, dictionaries or Stacks may be created).
class Stack3(Stack):
"""A last-in-first-out (LIFO) stack of items . """
# === Private attributes ===
# _items: The items stored in this stack . The FRONT of the _items Queue1 # represents the top of this stack .
_items: Queue1
def __init__ (self) -> None:
"""Initialize a new stack with no items . """ self ._items = Queue1()
def is_empty(self) -> bool:
"""Return whether this stack contains no items . """ return self ._items .is_empty()
def pop(self) -> Any:
"""Remove and return the item at the top of this stack . Preconditions: not self .is_empty()
"""
def push(self, item: Any) -> None:
"""Add the given item to the top of this stack . """