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.