DECEMBER 2018 EXAMINATIONS

CSC 108 H1F

Question 1. [6 marks]

Part 1: Select the option on the right that best describes what happens when the code on the left is run.

L = [1, 1, 2, 2, 3, 4]

for item in L:

if item % 2 == 1:

item = item + 1

print(L)

(A) [1, 1, 2, 2, 3, 4] is printed

(B) [2, 2, 2, 2, 4, 4] is printed

(C) A different list is printed

(D) An error occurs when the code is run

Part 2: Select the option on the right that best describes what happens when the code on the left is run.

L=['cat', 5, 'dog', 4]

f = open('output.txt', 'w')

for item in L:

f.write(str(item))

f.close()

f = open('output.txt', 'r')

print(f.readlines())

f.close()

(A) ['cat\n', '5\n', 'dog\n', '4\n'] is printed

(B) ['cat, '5', 'dog', '4'] is printed

(C) ['cat5dog4'] is printed

(D) A different list is printed

(E) An error occurs when the code is run

Part 3: Select the option on the right that best describes what happens when the code on the left is run.

s = 'big orange cats are best'

result = False

for each in s.split():

if each == 'cats':

result = True

else:

result = False

if result:

print('cats found')

else:

print('no cats found')

(A) cats found is printed

(B) no cats found is printed

(C) Something else is printed

(D) An error occurs when the code is run

Part 4: Select the option below that best describes what happens when this code is run.

shoes = ['Saucony', 'Asics', 'Asics', 'NB', 'Saucony', 'Nike', 'Asics', 'Adidas', 'Saucony', 'Asics']

shoes_to_places = {}

for i in range(len(shoes)):

shoes_to_places[shoes[i]].append(i + 1)

print(shoes_to_places)

(A) {'Saucony': [1, 5, 9], 'Asics': [2, 3, 7, 10], 'NB': [4], 'Nike': [6], 'Adidas': [8]} is printed

(B) {'Saucony': [0, 4, 8], 'Asics': [1, 2, 6, 9], 'NB': [3], 'Nike': [5], 'Adidas': [7]} is printed

(C) {'Saucony': [9], 'Asics': [10], 'NB': [4], 'Nike': [6], 'Adidas': [8]} is printed

(D) {'Saucony': [1], 'Asics': [2], 'NB': [4], 'Nike': [6], 'Adidas': [8]} is printed

(E) Something else is printed

(F) An error occurs when the code is run

Part 5:

Consider the following code.

D={'cat': 5}

x = VALUE1

D[x] = VALUE2

Circle ALL of the options below that could used be in place of VALUE1 so the code would run without error.

(A) 'dog'

(B) 'cat'

(C) x

(D) ['a', 'b']

(E) ('a', 'b')

(F) {'a': 'b'}

(G) D['cat']

(H) None of the above

Circle ALL of the options below that could used be in place of VALUE2 so the code would run without error.

(A) 'dog'

(B) 'cat'

(C) x

(D) ['a', 'b']

(E) ('a', 'b')

(F) {'a': 'b'}

(G) D['cat']

(H) None of the above

Question 2. [6 marks]

A board is a list of lists of length 1 strings, where each inner list has the same length. Precondition for all three functions below: the first parameter represents a board with at least one row and column.

Part (a) [1 mark] Complete the following function according to its docstring.

def get_row(board: List[List[str]], row_num: int) -> List[str]:

"""Return row row_num of board.

>>> b = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']]

>>> get_row(b, 0)

['a', 'b', 'c']

>>> get_row(b, 2)

['g', 'h', 'i']

"""

Part (b) [2 marks] Complete the following function according to its docstring.

def get_column(board: List[List[str]], column_num: int) -> List[str]:

"""Return column column_num of board.

>>> b = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']]

>>> get_column(b, 0)

['a', 'd', 'g']

>>> get_column(b, 2)

['c', 'f', 'i']

"""

Part (c) [3 marks] Complete the following function according to its docstring. Call at least one of the functions from Part (a) or Part (b) as a helper function.

def get_rotated_board(original: List[List[str]]) -> List[List[str]]:

"""Return a new board that is the same as board original but with its rows and columns swapped.

(Row 0 is swapped with column 0, row 1 is swapped with column 1, and so on.)

>>> b = [['a', 'a', 'a', 'a'], ['b', 'b', 'b', 'b'], ['c', 'c', 'c', 'c']]

>>> get_rotated_board(b)

[['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c']]

"""

Question 3. [5 marks]

A palindrome is a string that is read the same from front-to-back and back-to-front. For example, noon and racecar are both palindromes.

There are several ways to check whether a string is a palindrome. One algorithm compares the first letter to the last letter, the second letter to the second last letter, and so on, stopping when the middle of the string is reached or when a mismatch is found.

Part (a) [3 marks] Complete the function below using the algorithm described above. Do not modify code that is given outside of a box and do not add code outside of a box.

def is_palindrome(s: str) -> bool:

"""Return True if and only if s is a palindrome.

>>> is_palindrome('noon')

True

>>> is_palindrome('racecar')

True

>>> is_palindrome('dented')

False

"""

i=0

# In the box below, declare any additional variable(s), if needed

# In the box below, write the while loop condition

while                   :

# In the box below, write the while loop body

return i == len(s) // 2

Part (b) [1 mark] For a string s of length n, where n is divisible by 2, how many times will the while loop in is_palindrome iterate in the worst case?

Part (c) [1 mark] Circle the term below that best describes the worst case running time of the is_palindrome function.

constant                               linear                            quadratic                        something else

Question 4. [6 marks]

Complete the function below to according to its docstring.

def update_messages(msgs: List[str], lens: List[int]) -> None:

"""Update the list of the strings in msgs so their lengths are adjusted to

match the value at the corresponding position in lens. Strings that are too

long should be shortened by leaving off characters at the end and strings

that are too short should be lengthened by adding underscores to the end.

Precondition: len(msgs) == len(lens) and all values in lens are >= 0

>>> messages = ['aardvark', 'bear', 'cat', 'dog']

>>> update_messages(messages, [6, 5, 5, 3])

>>> messages

['aardva', 'bear_', 'cat__', 'dog']

>>> messages = ['', 'cat']

>>> update_messages(messages, [3, 0])

>>> messages

['___', '']

"""

Question 5. [6 marks]

Each of the functions below has a correct docstring, but one or more bugs in the code. In the table below each function, write two test cases. The first test case should not indicate a bug in the function (the test case would pass), while the second test case should indicate a bug (the test case would fail or an error would occur). If the code would stop due to an error on the second test case, write ‘Error’ in the Actual Return Value column for that test. Both test cases should pass on a correct implementation of the function.

def find_a_digit(s: str) -> int:

"""Return the index of the first digit in s, or the length of s if there are no digits.

"""

i=0

while not s[i].isdigit():

i=i+1

return i

Argument for s                         Actual Return Value                     Expected Return Value

Does not indicate bug (pass)

Indicates bug (fail/error)

def has_a_fluffy(s: str) -> bool:

"""Return True if and only if s contains at least one character that is in 'fluffy'.

"""

for ch in s:

if ch in 'fluffy':

return True

else:

return False

Argument for s                      Actual Return Value                   Expected Return Value

Does not indicate bug (pass)

Indicates bug (fail/error)

def get_year_of_study(num_credits: float) -> int:

"""Return the year of study at UofT given the number of credits num_credits, using these rules:

14.0 credits or more 4th year

9.0 to 13.5 credits 3rd year

4.0 to 8.5 credits 2nd year

< 4.0 credits 1st year

"""

if num_credits >= 4.0:

return 2

elif num_credits >= 9.0:

return 3

elif num_credits < 4.0:

return 1

else:

return 4

Argument for num_credits                  Actual Return Value                 Expected Return Value

Does not indicate bug (pass)

Indicates bug (fail/error)

Question 6. [6 marks]

Consider this function:

def mystery(s: str) -> str:

""" """

i=0

result = ''

while i < len(s) and not s[i] == '.':

result = result + s[i]

i=i+1

return result

Part (a) [1 mark]

Give an example of an argument of length 4 that would produce the best case behaviour of this function.

Part (b) [1 mark]

How many assignment statements would be executed on one call to this function with an argument of length 4 that produces the best case?

Part (c) [1 mark]

Circle the term below that best describes the best case running time of this function on a length n string.

constant                 linear               quadratic                  something else

Part (d) [1 mark]

Give an example of an argument of length 4 that would produce the worst case behaviour of this function.

Part (e) [1 mark]

How many assignment statements would be executed on one call to this function with an argument of length 4 that produces the worst case?

Part (f) [1 mark]

Circle the term below that best describes the worst case running time of this function on a length n string.

constant                     linear                          quadratic                         something else

Question 7. [12 marks]

Emotion analysis categorizes text as positive, negative, or neutral. For example, an emotion analysis program might categorize the text "happy birthday" as positive, and the text "it was disastrous" as negative.

Part (a) [4 marks]

Words are scored from -5 (most negative) to 5 (most positive). Word scoring data is stored in a comma separated values (CSV) file with a word, followed by its score, on each line.

Here is an example word scoring CSV file:

amazing,4

happy,3

anxious,-2

disastrous,-3

awesome,4

outstanding,5

woohoo,3

Each line in the file contains one word that contains only lowercase letters (no punctuation), followed by one comma, and then a valid score. There are no blank lines in the file. Each word has at least one character.

Neutral words, which would have a score of 0, are not included in the CSV file.

Given the example CSV file opened for reading, function read_word_scores should return:

{'amazing': 4, 'happy': 3, 'anxious': -2, 'disastrous': -3, 'awesome': 4, 'outstanding': 5, 'woohoo': 3}

Complete the function read_word_scores according to the example above and the docstring below. You may assume the argument file has the correct format.

def read_word_scores(f: TextIO) -> Dict[str, int]:

"""Return a dictionary that has words from f as keys and their

corresponding scores as values.

Precondition: words in f are unique

"""

Part (b) [4 marks] Complete the function below according to its docstring:

def score_document(text: str, word_to_score: Dict[str, int]) -> float:

"""Return the emotion analysis score for text. The score is the average of the score for

each word in text using word_to_score. If a word from text does not appear in word_to_score, its score is 0.

Precondition: text contains only words made up of only lowercase alphabetic characters

(no punctuation), and each word is separated by a space. text contains at least one word.

>>> word_to_score = {'amazing': 4, 'happy': 3, 'anxious': -2, \

'disastrous': -3, 'awesome': 4, 'outstanding': 5, 'woohoo': 3}

>>> score_document('everything is awesome', word_to_score)

1.3333333333333333

>>> score_document('outstanding and amazing', word_to_score)

3.0

>>> score_document('it is', word_to_score)

0.0

>>> score_document('i am happy but anxious', word_to_score)

0.2

"""

Part (c) [4 marks] Complete the function below according to its docstring:

def find_similar_words(word: str, word_to_score: Dict[str, int]) -> List[str]:

"""Return a list of words from word_to_score that are similar to word. Two words

are considered similar if they start with the same letter, have the same length,

and have the same score in word_to_scores. A word cannot be similar to itself.

Precondition: word is lowercase and word is in word_to_score

>>> word_to_score = {'amazing': 4, 'happy': 3, 'anxious': -2, \

'disastrous': -3, 'awesome': 4, 'outstanding': 5, 'woohoo': 3}

>>> find_similar_words('amazing', word_to_score)

['awesome']

>>> find_similar_words('happy', word_to_score)

[]

"""

Question 8. [6 marks]

Complete the function below to according to its docstring.

To receive full marks on this function, your solution must not remove any keys from the parameter card_to_total, even temporarily, such as by using the method dict.clear().

def update_amounts(card_to_total: Dict[str, int], amts: List[Tuple[str, int]]) -> None:

"""Update card_to_total with the amounts for each card from amts.

>>> D = {}

>>> update_amounts(D, [('visa', 1000), ('amex', 50), ('visa', 500)])

>>> D

{'visa': 1500, 'amex': 50}

>>> update_amounts(D, [('amex', 50), ('visa', 1000), ('mc', 100)])

>>> D

{'visa': 2500, 'amex': 100, 'mc': 100}

>>> update_amounts(D, [('paypal', 25), ('amex', -100)])

>>> D

{'visa': 2500, 'amex': 0, 'mc': 100, 'paypal': 25}

"""

Question 9. [7 marks]

Recall the algorithms insertion sort, selection sort, and bubble sort. Throughout this question, lists are to be sorted into ascending (increasing) order.

Part (a) [1 mark]

Consider the following lists:

L1 = [1, 3, 4, 5, 2, 6, 7, 8, 9]

L2 = [9, 8, 7, 6, 5, 4, 3, 2, 1]

Which list would cause Selection Sort to do more comparisons? Circle one of the following.

L1                      L2                       they would require an equal number

Part (b) [1 mark]

Consider the following lists:

L1 = [1, 3, 4, 5, 2, 6, 7, 8, 9]

L2 = [9, 8, 7, 6, 5, 4, 3, 2, 1]

Which list would cause Insertion Sort to do more comparisons? Circle one of the following.

L1                      L2                            they would require an equal number

Part (c) [5 marks] Consider the following lists. For each list, and each algorithm, consider whether at least two passes of the algorithm could have been completed on the list. If at least two passes could have been completed, check the box corresponding to that list and algorithm.

Insertion?              Selection?             Bubble?

[1, 2, 4, 6, 5, 7, 3]

[1, 3, 4, 6, 5, 7, 2]

[1, 3, 4, 5, 2, 6, 7]

[5, 4, 3, 2, 1, 6, 7]

[1, 2, 4, 5, 6, 7, 8]