csc108 dec 2010

21 Pages
152 Views
Unlock Document

Department
Computer Science
Course
CSC108H1
Professor
Dan Dolderman
Semester
Fall

Description
D N A P L E A S E H A N D I UNIVERSITY OF TORONTO H Faculty of Arts and Science E DECEMBER 2010 EXAMINATIONS S CSC 108 H1F A Instructors: Engels, Horton and E L Zingaro P Duration | 3 hours 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: / 6 # 2: / 4 # 3: /14 This ▯nal examination paper consists of 12 questions on 21 p# 4: (in/ 8ding this one). When you receive the signal to start, please make sure that your copy of the ▯nal examination is complete. # 5: / 8 Comments and docstrings are not required except where indica# 6: alt/ 8gh 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: / 6 You do not need to put import statements in your answers. # 8: / 8 You may not use break or continue on this exam. # 9: / 6 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/ 6to error-check. # 11: / 9 # 12: / 7 TOTAL: /90 Page 1 of 21 Good Luck! cont’d::: December 2010 Final Examination CSC 108 H1F Question 1. [6 marks] Beside each code fragment below, show the output that it would create. If it would generate an error say so, and give the reason why. Part (a) [1 mark] print -10 / 4 Part (b) [1 mark] print 24 - 12 / 4 - 2 Part (c) [1 mark] z = "over" + "and" print "..." + z * 3 + "..." Part (d) [1 mark] avg = 87.28196 print "Average is %.2f percent", % (avg) Part (e) [1 mark] s = "ya" for c in s: piece = "" for i in range(4): piece = piece + c * i + ":" print piece Part (f) [1 mark] s = "no" for i in range(4): piece = "" for c in s: piece = piece + c * i + ":" print piece Page 2 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F Question 2. [4 marks] Assume we have a game board consisting of n positions, and two objects: the hero and the enemy. (The game board has only one row.) At any point in time, the hero and the enemy will be a certain number of positions apart. Consider the number of spaces that the hero must move to land on the enemy’s position, as a fraction of the most the hero might have to move, n ▯ 1. That fraction is the distance between the hero and the enemy. It is positive if the enemy is to the right of the hero, negative if the enemy is to the left of the hero, and exactly 0 if the hero and enemy are on the same position. For example, consider the following game board where n = 6: hero enemy The distance here is 3=5, which is 0:6. For this game board with n = 5: enemy hero The distance is ▯0:25. Write the following function according to its docstring. def distance (game_board_size, hero, enemy): ’’’game_board_size is a positive int giving the number of positions on a game board. The positions are numbered from 0 to game_board_size-1. hero and enemy are ints giving valid hero and enemy positions on the game board, i.e., they are between 0 and game_board_size-1. Return a float between -1.0 and 1.0 giving the distance between hero and enemy.’’’ Page 3 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F Question 3. [14 marks] Consider strings where each character is one of the following three characters: ▯ g for \good" ▯ b for \bad" ▯ u for \unusable" The goodness of a string follows these two rules: ▯ The goodness of a string containing one or more u’s is 0. ▯ Otherwise, the goodness of a string is equal to the number of g’s in the string. For example, the goodness of "gbbgb" is 2, and the goodness of "gubgb" is 0. Remember that a slice of a string is a string, and so the goodness of a slice is de▯ned by these same rules. Any string has more than one slice you can take from it (unless it is a very short string). Each slice may have a di▯erent goodness value. Suppose we are only interested in slices of a particular length, and we want to ▯nd the one with the highest goodness. In part (c), you will write the following function according to its docstring. def best_slice (s, k): ’’’s is a str, k is an integer such that 0 <= k <= len(s). Return the starting index of the length-k slice of s with the highest goodness. If k is zero, return -1.’’’ Part (a) [3 marks] Assume that we want to test best_slice. Describe three test cases that each test di▯erent \categories" of inputs. To describe each test case, give the str and int that you would pass to best_slice, the return value you expect, and the purpose of the test case. Do not write any code. We have given you one test case as an example; add three more. Value of s Value of k Return value Purpose of this test case "" 0 -1 empty string Page 4 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F Part (b) [3 marks] Identify a function that would be a useful helper for best_slice. De▯ne it here, including a docstring. Part (c) [8 marks] Now write function best_slice. You do not need to repeat the docstring. def best_slice (s, k): Page 5 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F Question 4. [8 marks] A compressed string is a string where each alphabetic character is preceded by a single digit indicating the number of times that the character should be entered in the uncompressed version of the string. As a special case, if a character is to be entered only once, the compressed string may include the character c instead of 1c. For example: ▯ the compressed string 2a5b1c is uncompressed to aabbbbbc ▯ The compressed string 1ab2c is uncompressed to abcc ▯ The compressed string a9b3bc is uncompressed to abbbbbbbbbbbbc Write the following function according to its docstring. def uncompress (s): ’’’s is a compressed string. Return the corresponding uncompressed string.’’’ Page 6 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F Question 5. [8 marks] We can use a Python list to represent a table or matrix with rows and columns as follows. Each element of the list is itself a list, containing the items from one row of the table. For example, this table 5 10 15 1 2 3 10 20 30 2 4 6 is represented by this list in Python: [[5, 10, 15], [1, 2, 3], [10, 20, 30], [2, 4, 6]]. Notice that all the sublists have the same length. Write the following function according to its docstring. def sums(L): ’’’L is a list of lists of ints. All of L’s sublists have the same length. Return a new list that contains the sums of all the "columns" of L. For example, for the list [[5, 10, 15], [1, 2, 3], [10, 20, 30], [2, 4, 6]], return [18, 36, 54].’’’ Page 7 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F Question 6. [8 marks] A question bank is a text ▯le consisting of one or more multiple choice questions. Each multiple choice question consists of the following lines, in order: ▯ A line containing only the characters MC ▯ One line, containing the question ▯ One or more lines, containing possible answers to the question For example, here is a question bank with two questions. Notice that the number of answers to each question may be di▯erent. MC The instructor that has taught CSC108 the most is: Diane Dan Steve MC The funniest CSC108 instructor is: Dan Daniel Dan Z Daniel Z We want a function that will read such a ▯le and produce a list of strings, each of which contains the full text of one of the multiple-choice questions (including the answers). For example, the list produced from the ▯le above would be: [’The instructor that has taught CSC108 the most is:\nDiane\nDan\nSteve\n’, ’The funniest CSC108 instructor is:\nDan\nDaniel\nDan Z\nDaniel Z\n’] (Notice that the newlines are preserved.) Such a list could be used to choose random questions and generate a test, although you will not be writing any such code today. On the following page, write function read_mcqs according to its docstring. Page 8 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F def read_mcqs (f): ’’’f is an open question bank file with n >= 1 multiple choice questions. Return a list of n strings, each of which contains the entire question text and responses for one question.’’’ Page 9 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F Question 7. [6 marks] De▯ne the dictionary di▯erence between two dictionaries to be a new dictionary containing keys (and their values) that occur in one but not both of the dictionaries. If any key is in both original dictionaries, but with di▯erent values, it does not appear in the new dictionary. For example, if we have these two dictionaries: d1 = {1: ’a’, 2: ’b’, 3: ’c’, 9: ’h’} d2 = {1: ’k’, 6: ’f’, 2: ’g’, 5: ’e’, 8: ’c’} their di▯erence is {3: ’c’, 9: ’h’, 6: ’f’, 5: ’e’, 8: ’c’}. Write the following function according to the docstring and the de▯nition above. def dict_diff(d1, d2): ’’’d1 and d2 are dicts. Return a new dict which is the dictionary difference between d1 and d2.’’’ Question 8. [8 marks] In some games there are more than two dice, and the number of dice to roll can vary. We need a program that asks the user for a positive integer indicating how many dice to roll. If 0 is entered, the program stops; otherwise, the speci▯ed number of dice are rolled and the process is repeated. Here is a sample execution. Roll how many dice (0 to stop)? 4 2 2 4 5 Roll how many dice (0 to stop)? 2 1 6 Roll how many dice (0 to stop)? 1 5 Roll how many dice (0 to stop)? 0 This question continues on the next page. Page 10 of 21 Student #: cont’d::: December 2010 Final Examination CSC 108 H1F Below are 9 lines of code in random order. Your task is to use each of these lines at least once, and add the proper indentation, to arrive at a program that implements the above description. Do not add new code; simply copy and rearrange the given code. ▯ counter = counter + 1 ▯ counter = 0 ▯ while num_dice > 0: ▯ num_dice = int(raw_input ("Roll how many dice (0 to stop)? ")) ▯ while counter < num_dice: ▯ print random.randint (1, 6), ▯ print "" ▯ if __name__ == ’__main__’: ▯ import random Assemble the complete program here: Page 11 of 21 Student #: cont’d::: December 2010
More Less

Related notes for CSC108H1

Log In


OR

Join OneClass

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

Sign up

Join to view


OR

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.


Submit