CSC108H1S : Introduction to Computer Programming
Winter 2024
APRIL 2024 EXAMINATIONS
Short Python function/method descriptions:
int(x: object) -> int
Convert x to an integer, if possible. A floating point argument will be
truncated towards zero.
len(x: object) -> int
Return the length of list, tuple, dict, or string x.
max(iterable: object) -> object
max(a, b, c, ...) -> object
With a single iterable argument, return its largest item. With two or more
arguments, return the largest argument. Dictionary order used for str.
min(iterable: object) -> object
min(a, b, c, ...) -> object
With a single iterable argument, return its smallest item. With two or more
arguments, return the smallest argument. Dictionary order used for str.
open(name: str[, mode: str]) -> TextIO
Open a file. Legal modes are "r" (read) (default), "w" (write), and "a" (append).
print(values: object) -> None
Prints the values.
range([start: int], stop: int, [step: int]) -> list-like-object of int
Return the integers from start (inclusive) to stop (exclusive) with step
specifying the amount to increment (or decrement). If start is not specified,
the sequence starts at 0. If step is not specified, the values are incremented by 1.
type(x: object) -> the object's type
Return the type of the object x.
file open for reading (TextIO):
F.close() -> None
Close the file.
F.read() -> str
Read until EOF (End Of File) is reached, and return as a string.
F.readline() -> str
Read and return the next line from the file, as a string. Retain any newline.
Return an empty string at EOF (End Of File).
F.readlines() -> list[str]
Return a list of the lines from the file. Each string retains any newline.
file open for writing (TextIO):
F.close() -> None
Close the file.
F.write(x: str) -> int
Write the string x to F and return the number of characters written.
list:
list(x: object) -> list
Return an object converted to its list representation, if possible.
lst[ind: int] -> object
Produce the item at index ind in lst or an Index out of range error.
lst[start: int, stop: int, [step: int]] -> list
Produce a list containing every step items from lst, starting at index start,
going up to but not including index stop. (Default: step == 1)
x in L --> bool
Produce True if x is in L and False otherwise.
L.append(x: object) -> None
Append x to the end of the list L.
L.extend(iterable: object) -> None
Extend list L by appending elements from the iterable. Strings and lists are
iterables whose elements are characters and list items respectively.
L.index(value: object) -> int
Return the lowest index of value in L, but raises an exception if value does
not occur in S.
L.insert(index: int, x: object) -> None
Insert x at position index.
L.pop(index: int) -> object
Remove and return item at index (default last).
L.remove(value: object) -> None
Remove the first occurrence of value from L.
L.reverse() -> None
Reverse the list *IN PLACE*.
L.sort() -> None
Sort the list into non-decreasing order *IN PLACE*.
dict:
D[k] --> object
Produce the value associated with the key k in D or a Key error.
del D[k]
Remove D[k] from D.
k in D --> bool
Produce True if k is a key in D and False otherwise.
D.get(k: object) -> object
Return D[k] if k in D, otherwise return None.
D.items() -> list-like-object of Tuple[object, object]
Return the (key, value) pairs of D, as 2-tuples.
D.keys() -> list-like-object of object
Return the keys of D.
D.pop(k) -> object
Remove specified key from D and return the corresponding value.
D.values() -> list-like-object of object
Return the values associated with the keys of D.
str:
str(x: object) -> str
Return an object converted to its string representation, if possible.
s[ind: int] -> str
Produce the character at index ind in s or an Index out of range error.
s[start: int, stop: int, [step: int]] -> str
Produce a str containing every step characters from s, starting at index start,
going up to but not including index stop. (Default: step == 1)
x in s -> bool
Produce True if and only if string x is in string s.
S.isalpha() -> bool
Return True if and only if all characters in S are alphabetic
and there is at least one character in S.
S.isalnum() -> bool
Return True if and only if all characters in S are alphanumeric
and there is at least one character is S.
S.isdigit() -> bool
Return True if and only if all characters in S are digits
and there is at least one character in S.
S.islower() -> bool
Return True if and only if all cased characters in S are lowercase
and there is at least one cased character in S.
S.isupper() -> bool
Return True if and only if all cased characters in S are uppercase
and there is at least one cased character in S.
S.lower() -> str
Return a copy of the string S converted to lowercase.
S.replace(old: str, new: str) -> str
Return a copy of string S with all occurrences of the string old replaced with
the string new.
S.split([sep: str]) -> list[str]
Return a list of the words in S, using string sep as the separator and
any whitespace string if sep is not specified.
S.strip(chars: str) -> str
Return a copy of S with leading and trailing whitespace removed.
If chars is given and not None, remove characters in chars instead.
S.upper() -> str
Return a copy of the string S converted to uppercase.
1. [10 marks] Short answer
Each of the following interactions in the Python shell ends with an expression and blank space. For each one, write the value that would be displayed in the blank space, or the word NOTHING if nothing would be displayed. If evaluating the code would cause an error, (1) circle the part of the code that causes the error, (2) write the word ERROR beside the circle and (3) briefly explain why the error occurs. Then continue with the statements that follow.
>>> 1 + 2
>>> '1' + '2'
>>> 4 // 2
>>> 4 / 2
>>> x = 0
>>> if x < 1:
... x = x + 10
... elif x < 50:
... x = x + 200
... else:
... x = x + 3000
...
>>> x
>>> def f(x: int) -> int:
... """Docstring omitted."""
... x = x + 2
... return x
...
>>> x = 0
>>> f(x)
>>> x
>>> lst = [9, 6, 7]
>>> lst.sort().reverse()
>>> lst
>>> british_spelling = 'organise'
>>> american_spelling = british_spelling
>>> american_spelling[-2] = 'z'
>>> american_spelling
>>> british_word_list = ['organise', 'realise']
>>> american_word_list = british_word_list
>>> american_word_list[-2] = 'z'
>>> british_word_list
>>> american_word_list
>>> def g(x: list[int], y: list[int]) -> None:
... """Docstring omitted."""
... x[0] = x[0] + y[0]
... y[0] = x[0] - y[0]
...
>>> a = [3, 4]
>>> b = [5]
>>> g(a, b)
>>> a
>>> b
>>> d = {}
>>> d['fish'] = ['swim']
>>> 'swim' in d
>>> d['penny'] = d['fish']
>>> len(d)
>>> d['tom'].append('skate')
>>> len(d)
>>> d['tom'] = ['run']
>>> len(d)
2. [9 marks] Function writing
Write a complete function named has_alpha_order that takes a list of str as a parameter.
The function has_alpha_order should return True if and only if the items in the given list are in alphabetical order. The case of letters in strings should be ignored when they are compared. That is, the string 'apple' should be considered to come before the string 'BANANA', despite the fact that the value of the Python expression 'apple' < 'BANANA' is False.
The function should assume that the str in the given list only contain alphabetic characters.
Your complete function must include:
• a complete header with appropriate type annotations,
• a complete docstring that includes a proper description, preconditions and at least two suitable examples,
• and a correct function body.
3. [10 marks] Lists and Dicts
(a) [6 marks] The function in this question works with a nested list of data about students. Each item in the inner list contains the following information about an individual student in the order:
• the student’s name (a str)
• the student’s college (a str)
Complete the following function according to its docstring.
def group_valid(group: list[list[str]], max_group_size: int) -> bool:
"""Return True if and only if group meets all of the following conditions
for being a valid group of students:
- group contains at most max_group_size students
- all students in the group are in the same college
- no two students in the group have the same name
Each sublist in group contains the following information about a student,
in order: name (a str), college (a str)
Preconditions:
- len(group) > 0
- len(group[i]) == 2 for each value of i in range(len(group))
>>> g1 = [['mohi', 'sgs'], ['laura', 'sgs'], ['fernando', 'sgs']]
>>> group_valid(g1, 5)
True
>>> group_valid(g1, 2) # group too big
False
>>> g2 = [['jen', 'oise'], ['paul', 'trn'], ['sadia', 'oise']]
>>> group_valid(g2, 3) # not all in same college
False
>>> g3 = [['david', 'vic'], ['tom', 'vic'], ['david', 'vic']]
>>> group_valid(g3, 8) # two 'david's
False
"""
(b) [4 marks] Complete the following function according to its docstring. Be sure to make use of the constants that are defined before the function definition.
EVEN = 'even'
ODD = 'odd'
def get–properties(nums: list[int]) -> dict[int, str]:
"""Return a dictionary in which each key is an item from nums and its value is one of the constants EVEN or ODD, depending on whether the item is
even or odd, respectively . If nums is the empty list, return an empty
dictionary .
>>> nums = [1, 2, 9, 8, 8, 6, 1]
>>> result = get–properties(nums)
>>> result == {1: ODD, 2: EVEN, 9: ODD, 8: EVEN, 6: EVEN}
True
>>> get–properties([])
{}
"""
4. [10 marks] Files
The course coordinator is interested in learning more about how students used the radical generosity late policy this term with Assignment 3. Comma Separated Value (CSV) files were used to keep track of extension requests. These files have the following format:
• The first line of the file contains information about the course, the term and the section.
• The second line of the file contains descriptions of each column of data on the remaining line(s).
• The remaining line(s) of the file contain information about each extension request. Each of these lines has the format:
— student number followed by a comma (',')
— student name followed by a comma (',')
— number of days of extension followed by the newline character ('\n')
As an example, the file named csc108-1 .csv given below follows the specifications described above:
"CSC108 Winter 2024 Section 1",,
student number,student name,extension days
81235,Mary Simon,1
91112,Julie Payette,28
72341,David Johnston,64
18181,Michaelle Jean,1
35810,Adrienne Clarkson,10
Note:
• in this example, students could receive an extension of more than 7 days.
• the newline characters are not displayed. They cause data about each student to begin on a new line.
In the questions that follow, you may assume that extension data files are correctly formatted and follow the specifications described above. Also assume that at least one student requested an extension of at least 1 day. Also assume that each student’s number and name appears at most once in an extension data file.
(a) [6 marks] Complete the following function according to its docstring:
from typing import TextIO
def maximum–extension(data–file: TextIO) -> int:
"""Return the maximum number of days of extension recorded in the radical generosity extension file data–file .
The parameter data–file refers to a file that has been opened for reading .
>>> my–file = open('csc108-1.csv')
>>> maximum–extension(my–file)
64
>>> my–file.close()
"""
(b) [4 marks] Since there are 7 separate lecture sections of CSC108, the course coordinator has orga- nized students by lecture section, and has kept 7 separate extension request files. The file names are csc108-1 .csv, csc108-2 .csv, csc108-3 .csv, . . . , csc108-7 .csv. Assume that these files have the correct format and that at least one student requested an extension in each section. The following function is to be used to determine the maximum extension across all sections of CSC108.
Complete the following function according to its docstring. In your solution, you must call the function maximum extension as a helper function. You may assume that the function maximum extension has been correctly implemented.
def maximum– course–extension(course–name: str, num – sections: int) -> int:
"""Return the maximum number of days of extension recorded across all of
the radical generosity extension files for course course–name that has
num – sections sections .
Assume that the extension file names have the format:
course–name followed by ' - ' followed by the section number followed by ' .csv' Assume that the section numbers are 1 through num – sections, inclusive .
>>> maximum–course–extension('csc108', 1)
64
>>> maximum– course–extension('csc108', 7) # assume the given result is correct 144
"""
5. [10 marks] Testing
In this question, you are to consider the problem of testing the function frequencies. This function has the following header and docstring:
def frequencies(s: str) -> dict[str, int]:
"""Return a dictionary in which each key is a single character from s
and its value is the number of times that character occurs in s . If s
is the empty string, return an empty dictionary . Each different character
in s appears as a key in the returned dict .
>>> frequencies('loop') == {'l': 1, 'o': 2, 'p': 1}
True
>>> frequencies('') == {}
True
"""
(a) [3 marks] In the table below, we have outlined one test case for frequencies. Add three more test cases that could be part of a complete set of cases for thoroughly testing the function. Do not include duplicate test cases.
|
Test Case Description
|
s
|
Expected Return Value
|
|
empty string
|
''
|
{}
|
|
|
|
|
|
|
|
|
(b) [3 marks] Complete the following module by writing appropriate pytest functions for the test cases proposed in Part (a). Complete the function headers, add docstring descriptions (with no examples) and add function bodies.
"""Unit tests for the function frequencies . """
import pytest
def test–empty– string() -> None:
"""Test that an empty dictionary is returned when the argument
is the empty string .
"""
assert frequencies('') == {}
def
def
def
if ––name–– == ' ––main–– ':
# Perform the unit tests using pytest
pytest.main(['test–frequencies.py'])
(c) [1 mark] Would it be appropriate to add a pytest function that tests whether the function frequencies mutates its argument? Answer yes or no and briefly justify your response.
(d) [1 mark] Here is a buggy implementation of the frequencies function.
def frequencies(s: str) -> dict[str, int]:
"""Return a dictionary in which each key is a single character from s
and its value is the number of times that character occurs in s . If s
is the empty string, return an empty dictionary . Each different character
in s appears as a key in the returned dict .
>>> frequencies('loop') == {'l': 1, 'o': 2, 'p': 1}
True
>>> frequencies('') == {}
True
"""
d = {}
for character in s:
if character in d:
d[character] += 1
else:
d[character] = 0
return d
Fill in the two boxes below with values chosen to demonstrate that this implementation contains a bug.
>>> actual = frequencies( )
>>> expected = { }
>>> actual == expected
False
(e) [2 marks] What is the bug in the above function body and how could it be fixed?
6. [11 marks] Sorting, Searching and Runtime
(a) [1 mark] In the list below, 4 passes of the bubble sort algorithm have been completed, and the double bar separates the sorted part of the list from the unsorted part. The item at index 0 is missing. Fill in the missing item with an appropriate value that will cause bubble sort to make the most number of interchanges on the next pass of the algorithm.
(b) [1 mark] In the list below, 4 passes of the insertion sort algorithm have been completed, and the double bar separates the sorted part of the list from the unsorted part. The item at index i is missing. Fill in the missing item with a value that will cause insertion sort to move the most number of items on the next pass of the algorithm.
(c) [1 mark] In the list below, 4 passes of the insertion sort algorithm have been completed, and the double bar separates the sorted part of the list from the unsorted part. The item at index i is missing. Fill in the missing item with a value that will cause insertion sort to move the fewest number of items on the next pass of the algorithm.
(d) [1 mark] In the list below, 4 passes of the selection sort algorithm have been completed, and the double bar separates the sorted part of the list from the unsorted part. The item at index i is missing. Fill in the missing item with a value that will cause selection sort to interchange this value with the value 9 on the next pass of the algorithm.
A friend has given you a Python list that has length n and has told you that it contains each of the integers between 0 and n except for one integer. They challenged you to figure out which integer was missing. (Note that there are n + 1 integers between 0 and n, inclusive. The list has length n.)
A recent graduate of CSC108 wrote the following Python function to solve the puzzle:
def my – search(lst: list[int]) -> int:
"""Return the integer between 0 and len(lst) that does not appear in lst .
Preconditions:
- len(lst) > 0
- 0 <= lst[i] <= len(lst) for each value of i in range(len(lst))
- the items in lst are all different
>>> my–search([5, 2, 0, 1, 4])
3
>>> my–search([1])
0
"""
for i in range(len(lst) + 1):
# Search lst for i . Return i when i is not found .
found– i = False
for j in range(len(lst)):
if i == lst[j]:
found– i = True
print(i, j, lst[j]) # print statement to produce data for table if not found– i:
return i
(e) [2 marks] Suppose the function call my search([3, 0, 2]) is executed. Complete the following table to show the values of i, j and lst[j] that would be printed when the code is evaluated. Write the values in the same order as they would be printed. We have completed the first row for you. You may not need all of the rows in the table.
(f) [1 mark]
Fill in the first box below with an argument list of size 4 for which the call to my search exhibits its best case (i.e., fastest) running time for a list of size 4. Fill in the second box with value returned by the function call.
>>> my–search( )
(g) [1 mark]
Fill in the first box below with an argument list of size 4 for which the call to my search exhibits its worst case (i.e., longest) running time for a list of size 4. Fill in the second box with value returned by the function call.
>>> my–search( )
(h) [1 mark] Circle the term below that best describes the worst case running time of the function
my search:
constant linear quadratic something else
Another approach!
A different graduate of CSC108 wrote the following Python function to solve the puzzle:
def puzzle– search(lst: list[int]) -> int:
"""Return the integer between 0 and len(lst) that does not appear in lst .
Preconditions:
- len(lst) > 0
- 0 <= lst[i] <= len(lst) for each value of i in range(len(lst))
- the items in lst are all different
>>> puzzle–search([5, 2, 0, 1, 4])
3
>>> puzzle–search([1])
0
"""
# make a list for keeping track of found numbers
found–list = []
for i in range(len(lst) + 1):
found–list.append(False)
# note which numbers appear in lst
for number in lst:
found–list[number] = True
# return the number that was not found
for i in range(len(lst) + 1):
if not found–list[i]:
return i
(i) [1 mark] If len(lst) == n, and the missing number is n, what is the total number of loop iterations performed by the function puzzle search()? Include the iteration in which the value is returned. (Your answer should be a formula that involves n.)
(j) [1 mark] Circle the term below that best describes the worst case running time of the function puzzle search:
constant linear quadratic something else