COMP10001 Foundations of Computing

Final Exam, Semester 1 2023

Instructions to Students: This exam contains 100 marks, and counts for 50% of your final grade. Be sure to write your student number clearly in all places where it is requested.

This assessment is closed book, and you may not make use of any printed, written, electronic, or online resources.

All questions should be answered in the spaces provided on the exam paper.  There is also an overflow page available at the end of the paper. If you write any answers there, be sure to also write the corresponding question number.

There are a number of places where you are asked for a single Python statement, but two or more answer lines are provided.  In these cases you may draft your answer in one line and then copy it neatly to another line within the answer boxes if you wish, but if you do so you must then cross out the first draft answer.

You must not communicate with any other student in any way from the moment you enter the exam venue until after you have left the exam venue. All phones and other network, communication, and electronic devices must be switched completely off while you are in the exam room.

All material that is submitted as part of this assessment must be completely your own unassisted work, and undertaken during the time period allocated to the assessment.

Calculators and dictionaries are not permitted.

In your answers you may make use of built-in functions, but may not import functions from any other libraries.

You may use any blank pages to prepare drafts of answers, but you must copy those answer onto the correct answer box before the end of the exam.

Question 1 (20 marks)

Each subquestion is worth 2 marks. To get full marks you must specify both the correct value and be clear in your answer that you understand what the type will be. If you think an expression is not legal according to the rules of Python, you should write “Error” in the box. If you want to include any blanks in output strings, draw one  symbol for each blank character.

(a)    2  +  3  *  4  //  5

(b)    4  -  12  %  5  *  3

(c)     [1,  3,  4]  *  3

(d)    "a"  +  "fine"  +  "day"

(e)    "sunshine"[2:5]

(f)    (1,  2,  5,  4,  8,  7)[2:][1]

(g)    sorted("raining")

(h)    [x/2  for  x  in  range(1,5)]

(i)    set("apples")  -  set("peas")

(j)    (False,)  *  (True  +  True)

Question 2 (20 marks)

Each subquestion is worth 4 marks. There are two lines provided for each answer, but you should give a single Python assignment statement if you can.   If your answer requires more than one assignment statement you will be eligible for partial marks.

(a)    Suppose that vals is a Python list. Give a Python assignment statement that assigns True to even   size if vals has an even number of items in it, and assigns False if not.

(b)    Suppose that vals is a Python list of numbers.   Give a Python assignment statement that assigns True to all equal if all of the values in vals are the same, and assigns False if not.

(c)    Suppose that n is a positive integer.  Give a Python assignment statement that creates a list list of tup containing n tuples, with each tuple containing n values all of which are zeros.

(d)    Suppose that text is a Python string.  Give a Python assignment statement that assigns the number of digit characters in text to the variable n digits.

(e)    Suppose that nums is a Python list of numbers. Give a Python assignment statement that cre- ates a new version of nums in which 1 has been added to the first element in nums, 2 has been added to the second element, 3 to the third element, and so on through the remaining elements.

Question 3 (15 marks)

The following function reformats text so that input lines of any length are formed into a paragraph in which all of the lines are of roughly equal length, except for the last one.

def formatter(lines, linelen=DEF_LINE_LEN): # 01 ’’’ Takes input ‘lines‘ and restructures their words into output lines that are as long as possible without exceeding ‘linelen‘, creating a left-justified formatted paragraph. Adjacent whitespaces are replaced by single blanks; output lines start/end with non-blanks; and too-long-words are placed on lines by themselves and allowed to break the right margin. ’’’ # first break the input into a sequence of words XXXXXXXXXX # 02 for line in lines: # 03 XXXXXXXXXX # 04 all_words += words # 05 # then build the output lines out_lines = [] # 06 out_line = "" # 07 XXXXXXXXXX # 08 # try and fit the next word XXXXXXXXXX # 09 # can’t place next word, so need to start a new line out_lines.append(out_line) # 10 out_line = "" # 11 # now know we should have space in out_line if len(out_line) > 0: # 12 out_line += " " # 13 out_line += word # 14 # might still have a partial line XXXXXXXXXX # 15 out_lines.append(out_line) # 16 # all done, time to finish up return out_lines # 17

There are five locations in the function where one line of Python code has been replaced by XXXX symbols. The number of X’s should not be used as an indication of the length of the text that has been covered up.

In the boxes below, write the Python statement that has been covered up at each of the named locations. Each subquestion is worth 3 marks.

(a)    What has been covered up at line 02? 

(b)    What has been covered up at line 04?

(c)    What has been covered up at line 08?

(d)    What has been covered up at line 09?

(e)    What has been covered up at line 15?

Question 4 (15 marks)

Consider the following Python function, which is designed to find the most frequently occurring vowel in some given string text. There are five vowels in English: a, e, i, o, and u.

def most_freq_vowel(text): # 01 ’’’ Return the most frequently occurring vowel in ‘text‘ in a case insensitive manner (that is, ’a’ should be counted the same as ’A’). If there is a tie, return the vowel that appears first in the English alphabet, and if there are no vowels at all, return None. ’’’ vowels = "eeiou" # 02 counts = {} # 03 for char in text: # 04 if char in vowels: # 05 counts[char] += 1 # 06 if len(counts) != 0: # 07 return None # 08 max_count = max(counts.values()) # 09 for vowel in vowels: # 10 if counts[vowel] > 0 and counts[vowel] == max_count: # 11 return vowel # 12 return None # 13

Unfortunately, the function contains a number of errors. The subquestions on the next two pages are designed to help you first identify those errors, and then correct them.

(a)    [4 marks] Trace the computation that is performed for the function call

most_freq_vowel("hello")

to determine what is returned.  Show both the value and type in the answer that you provide.  Or, if you think an exception will be raised before the function returns, indicate in English what error will arise (for example, “divide by zero”, or “index out of range”, or “invalid method for type int”, and so on).

Now write the output that should have been returned for that input if the function was working correctly.

Finally, identify a minimal fix for this error, by giving exactly one line number in the code that is to change, and then providing one replacement line that corrects the error.

(b)    [4 marks] Next, trace the function call

most_freq_vowel("fly")

to determine what is returned (or, if the function does not return, describe the error that occurs), providing the same details required in part (a).

Now write the output that should have been returned for that input if the function was working correctly.

Finally, identify a minimal fix for this error, by giving exactly one line number in the code that is to change, and then providing one replacement line that corrects the error.

(c)    [4 marks] There are two further errors present in the function that are not revealed by the tests shown in parts (a) and (b) of this question. In answering this part of the question, you should assume that the errors already identified in parts (a) and (b) have been fixed.

Write a function call that would expose one of these other two errors (you may choose either).

Describe what the result of that function call should be, and what it would actually be as a result of this error.

Finally, identify a minimal fix for this error, by giving exactly one line number in the code that is to change, and then providing one replacement line that corrects the error.

(d)    [3 marks] Now locate the other error in the function, and briefly describe it in one sentence. You do not need to give a function call that would expose this error.

Now identify a minimal fix for this error, by giving exactly one line number in the code that is to change, and then providing one replacement line that corrects the error.

Question 5 (30 marks)

Recall the Matching Game from Assignment  1, which featured a number of colored pieces on a two-dimensional board, with the board represented in Python by a list of lists.  Each piece was represented as a string containing a single upper-case character between ’A’ and ’Y’ . The character ’Z’ was used to indicate a blank position on the board.  For example, a board might have four columns and three rows and look like this:

board  =  [[’B’,  ’G’,  ’B’,  ’Y’], 

                [’G’,  ’B’,  ’Y’,  ’Y’], 

                [’G’,  ’G’,  ’Y’,  ’Z’]]

In this question you will implement a number of “powerups” – functions that manipulate the board in ways that would not normally be permitted by the rules of the game.  You are not required to include comments or docstrings in your functions, but may if you wish.

(a)    [6 marks] Write a Python function row_destroyer(board,  row)

that takes two parameters:  board, a list of lists representing a game board; and row, the index position of a row on the board. You may assume that row has a valid value for the given board.

Your function should alter the board so that all of the pieces in the row specified by row are replaced by blanks (that is, the character ’Z’).

For example:

>>> board  =  [[’B’,  ’G’,  ’B’],  [’G’,  ’B’,  ’Y’],  [’G’,  ’G’,  ’Y’]]

>>>  row_destroyer(board,  1)

>>> print(board)

[[’B’,  ’G’,  ’B’],  [’Z’,  ’Z’,  ’Z’],  [’G’,  ’G’,  ’Y’]]

(b)    [8 marks] Now write a Python function piece_destroyer(board, piece)

that takes two parameters: board, a list of lists representing a game board; and piece, a single- character string representing a piece.

Your function should alter the board so that all pieces that have the same color as piece are replaced by blanks (that is, the character ’Z’).

For example:

>>> board  =  [[’B’,  ’G’,  ’B’],  [’G’,  ’B’,  ’Y’],  [’G’,  ’G’,  ’Y’]]

>>> piece_destroyer(board,  ’B’)

>>> print(board)

[[’Z’,  ’G’,  ’Z’],  [’G’,  ’Z’,  ’Y’],  [’G’,  ’G’,  ’Y’]]

(c)    [8 marks] Now write a Python function put_in_order(board)

that takes one parameter: board, a list of lists representing a game board.

Your function should rearrange the pieces on the board so that they are placed in alphabetically sorted order starting from the lowest index position.

Here are two possible execution sequences:

>>> board  =  [[’A’,  ’C’,  ’E’],  [’D’,  ’F’,  ’H’],  [’B’,  ’G’,  ’I’]]

>>> put_in_order(board)

>>> print(board)

[[’A’,  ’B’,  ’C’],  [’D’,  ’E’,  ’F’],  [’G’,  ’H’,  ’I’]]

>>> board  =  [[’B’,  ’G’,  ’B’],  [’G’,  ’B’,  ’Y’],  [’G’,  ’G’,  ’Y’]]

>>> put_in_order(board)

>>> print(board)

[[’B’,  ’B’,  ’B’],  [’G’,  ’G’,  ’G’],  [’G’,  ’Y’,  ’Y’]]

(d)    [8 marks] Finally, write a Python function

connected_destroyer(board,  row,  col)

that takes three parameters: board, a list of lists representing a game board; row, an index value for a row in the board; and col, an index value for a column in the board.  You may assume that row and col have valid values for the given board.

Your function should modify the board such that the piece at row, col is replaced by a blank (’Z’).

Furthermore, any piece that is immediately above, below, left or right of a piece that was replaced and has the same color as the piece that was replaced should also be replaced by a blank.

This process should continue until no more replacements are possible.

Here are three possible execution sequences:

>>> board  =  [[’B’,  ’B’,  ’A’],  [’B’,  ’A’,  ’A’],  [’A’,  ’A’,  ’B’]]

>>>  connected_destroyer(board,  0,  0)

>>> print(board)

[[’Z’,  ’Z’,  ’A’],  [’Z’,  ’A’,  ’A’],  [’A’,  ’A’,  ’B’]]

>>> board  =  [[’B’,  ’B’,  ’A’],  [’B’,  ’B’,  ’A’],  [’A’,  ’A’,  ’B’]]

>>>  connected_destroyer(board,  1,  1)

>>> print(board)

[[’Z’,  ’Z’,  ’A’],  [’Z’,  ’Z’,  ’A’],  [’A’,  ’A’,  ’B’]]

>>> board  =  [[’B’,  ’B’,  ’B’],  [’B’,  ’A’,  ’B’],  [’B’,  ’B’,  ’A’]]

>>>  connected_destroyer(board,  0,  0)

>>> print(board)

[[’Z’,  ’Z’,  ’Z’],  [’Z’,  ’A’,  ’Z’],  [’Z’,  ’Z’,  ’A’]]