[SOLVED] CSC110Y1F Final Examination 2022 Python

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