Dec 2012.pdf

20 Pages
Unlock Document

Computer Science
Dan Dolderman

D N A P L E A S E H A N D I N H UNIVERSITY OF TORONTO E Faculty of Arts and Science DECEMBER 2012 EXAMINATIONS S A CSC 108 H1F E Instructors: Campbell, Craig, and LungL Duration | 3 hours P Examination Aids: None Student Number: Family Name(s): Given Name(s): Do not turn this page until you have received the signal to start. In the meantime, please read the instructions below carefully. # 1: / 8 # 2: / 4 # 3: / 2 This ▯nal examination paper consists of 12 questions on 20 p# 4: (in/ 4ding this one). When you receive the signal to start, please make sure that your copy of the ▯nal examination is complete. # 5: / 5 Comments and docstrings are not required except where indica# 6: alt/10gh they may help us mark your answers. They may also get you part marks if you can’t ▯gure out how to write the code. # 7: / 5 You do not need to put import statements in your answers. # 8: / 9 You may not use break or continue on this exam. # 9: /10 If you use any space for rough work, indicate clearly what you want marked. Assume all input is valid unless otherwise indicated; there# 10:o ne/10to error-check. # 11: / 3 # 12: / 2 TOTAL: /72 Page 1 of 20 Good Luck! cont’d::: December 2012 Final Examination CSC 108 H1F Question 1. [8 marks] For each code fragment in the table below, indicate whether or not the code causes an error. If it runs without error, give the output. If it has an error, explain the cause of the error. Code Error? Output or Cause of Error (yes or no) print(9 / 5) print(9 // 5) print(9 % 5) a = [1, 2, 3, 4, 5] print(a[5]) b = [’hello’, ’world’] print(b[2]) c = ’moogah’ c[0] = ’b’ print(c[0]) d = f2: [’sam’, ’pat’, ’carl’], 0: [’little’, ’bo’, ’peep’], 1: [’tina’, ’jo’]g print(d[0][-1][1:]) e = [’A’, ’B’, ’C’] e[0] = 8663 print(e) Page 2 of 20 cont’d::: December 2012 Final Examination CSC 108 H1F Question 2. [4 marks] In the box below, write what is printed when the following program is executed. def square(x): print(’Squaring’, x) return x * x def add(y, z): print(’Adding’, y, z) return y + z if add(-25, square(5)) > 0 and add(-4, square(10)) > 0: print(’Woohoo!’) else: print(’Rats’, add(square(3), 0)) Page 3 of 20 Student #: cont’d::: December 2012 Final Examination CSC 108 H1F Question 3. [2 marks] The following function does not always do what the docstring claims (although the type contract is correct). def filter_positives(L): ’’’(list of int) -> list of int Return a new list containing the elements of L that are positive (greater than 0). ’’’ acc = [] for item in L: if item <= 0: return acc else: acc.append(item) return acc In the table below, write the simplest possible test case that reveals the problem. Test Case Description L Expected Return Actual Return Value According Value Based to Docstring on Code Page 4 of 20 cont’d::: December 2012 Final Examination CSC 108 H1F Question 4. [4 marks] Consider the following code. def my_function(x, y): x.append(5) y = y + [5] x = [1, 2, 3] x1 = x x2 = x[:] y = [1, 2, 3] y1 = y y2 = y[:] my_function(x, y) Once this code has been executed, what are the values that the variables now refer to? Variable Value x x1 x2 y y1 y2 Page 5 of 20 Student #: cont’d::: December 2012 Final Examination CSC 108 H1F Question 5. [5 marks] Some, but not all, of the lines containing a comment can be reached. All of these comment lines have this form, where X is a number: # Condition X In the table at the bottom of this page, complete each row by specifying one set of inputs to the function that will cause the comment line to be reached. If there are no possible inputs that would allow a particular comment to be reached, indicate this with ’X’s in the corresponding table row cells. If the value of a variable is not relevant, write ’ANY’ in the corresponding table row cell. We have ▯lled in the ▯rst two rows for you so that you can see what we want. def mystery_code_paths(b1, b2, i, s): ’’’(bool, bool, int, str) -> NoneType’’’ if False: # Condition 0 elif b1: # Condition 1 if (b1 or b2) and i == 0: if i < 0: # Condition 2 elif b1: # Condition 3 elif not b1 and not b2: # Condition 4 elif len(s) == i: # Condition 5 else: # Condition 6 Condition b1 b2 i s 0 X X X X 1 True ANY ANY ANY 2 3 4 5 6 Page 6 of 20 cont’d::: December 2012 Final Examination CSC 108 H1F Question 6. [10 marks] Word ladder is a single-player game in which a player tries to link an initial word (e.g., cold) to a goal word (e.g., warm) by ▯nding a chain of words to link the two. Words next to each other in the chain must di▯er by exactly one letter. For example: cold ! cord ! card ! ward ! warm. This question has you write a word ladder game. We ▯rst have you write two helper functions, and in the last part you will write a main program. Part (a) [3 marks] Write the body for function differ_by_one. def differ_by_one(word1, word2): ’’’ (str, str) -> bool Return True iff word2 can be formed from word1 by changing exactly one letter. >>> differ_by_one(’cat’, ’cot’) True >>> differ_by_one(’abc’, ’aBc’) True >>> differ_by_one(’abc’, ’abc’) False >>> differ_by_one(’abc’, ’abcd’) False ’’’ Page 7 of 20 Student #: cont’d::: December 2012 Final Examination CSC 108 H1F Part (b) [2 marks] Write the body for function get_word_list. def get_word_list(word_file): ’’’ (io.TextIOWrapper) -> list of str word_file contains one word per line. Return a list that contains each word from word_file with leading and trailing whitespace removed. ’’’ Part (c) [5 marks] Complete the main program on the next page. Avoid duplicate code by calling function differ by one as a helper. You should do this even if your differ one is incomplete/incorrect and the program will be marked as though it works correctly. To play the game, the player repeatedly guesses the next word in the chain. If the word entered is not valid (it does not di▯er from the current word by exactly one letter or it does not appear in the ▯le of words), the player is prompted to re-enter a word until a valid word is entered. Once a valid word is entered, if it is the goal word, the game ends. If it is not the goal word, the player is prompted to make another move using the word they just formed as the current word. The player continues to make moves until the goal word is formed. The object of the game is to form the goal word in as few moves as possible, so the number of moves is tracked (only valid moves are counted). Page 8 of 20 cont’d::: December 2012 Final Examination CSC 108 H1F print("Welcome to word ladder!") initial = ’cold’ current = initial goal = ’warm’ # one possible solution is cold -> cord -> card -> ward -> warm num_moves = 0 word_file = open(’words.txt’) word_list = get_word_list(word_file) word_file.close() while current != goal: print("Current: ", current, ", Goal: ", goal) next_move = input("Please enter the next word in the chain: ") print("You solved the word ladder in", num_moves, "moves!") Page 9 of 20 Student #: cont’d::: December 2012 Final Examination CSC 108 H1F Question 7. [5 marks] Consider a dictionary where each key is a 3-element tuple containing the name of a sports team, its city, and its sport, and each value is the number of wins for that team. For example: d = {(’Raptors’, ’Toronto’, ’basketball’): 10, (’Blues’, ’Toronto’, ’basketball’): 21, (’Senators’, ’Ottawa’, ’hockey’): 45, (’Leafs’, ’Toronto’, ’hockey’): 3} The header for function get_wins_by_category appears below. It has two parameters: ▯ the ▯rst parameter, team_to_wins, is a dictionary of the form described above, and ▯ the second parameter, category, is a string: one of ’name’, ’city’, or ’sport’. get_wins_by_category returns a new dictionary based on team_to_wins in which the keys are either the names, cities or sports (as speci▯ed by category) and the values are the total number of wins associated with each key. Here is a sample shell interaction that uses variable d, initialized above. >>> get_wins_by_category(d, ’city’) {’Toronto’: 34, ’Ottawa’: 45} Complete function get_wins_by_category. Use good style: avoid duplicate code. def get_wins_by_category(team_to_wins, category): ’’’(dict of {tuple of (str, str, str): int}, str) -> dict of {str: int}’’’ Page 10 of 20 cont’d::: December 2012 Final Examination CSC 108 H1F Question 8. [9 marks] Function remove_dup_values takes a dictionary d of {int: int} as input, removes from that dictionary all the entries whose values are not unique and returns the number of entries that were removed. In other words, whenever two (or more) entries in d have the same value, then all those entries are removed from d. Part (a) [4 marks] In the table below, we have outlined one test case for remove_dup_values. Add four more test cases chosen to test the function as thoroughly as possible. Test Case Description Dictionary Before Call Dictionary After Call Return Value empty dictionary {} {} 0 single item dictionary {1: 4} {1: 4} 0 Part (b) [5 marks] Write the function body. def remove_dup_values(d): ’’’ (dict of {int: int}) -> int Remove all entries of d whose values are not
More Less

Related notes for CSC108H1

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.