CSC108 Final 2011S

P
L
E
A
S
E
H
A
N
D
I
N
UNIVERSITY OF TORONTO
Faculty of Arts and Science
SUMMER 2011 EXAMINATIONS
CSC108 H1Y
Instructors: Janicki
Duration 3 hours
P
L
E
A
S
E
H
A
N
D
I
N
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.
This nal examination paper consists of 11 questions on 20 pages (including
this one). When you receive the signal to start, please make sure that your
copy of the nal examination is complete.
Comments and docstrings are not required except where indicated, although
they may help us mark your answers. They may also get you part marks if
you cant gure out how to write the code.
You may not use break or continue on this exam.
If you use any space for rough work, indicate clearly what you want marked.
Assume all input is valid unless otherwise indicated; there is no need to
error-check.
# 1: / 6
# 2: / 8
# 3: /12
# 4: / 5
# 5: / 5
# 6: / 7
# 7: /11
# 8: / 7
# 9: /13
# 10: / 6
# 11: / 8
TOTAL: /88
Page 1 of 20 Good Luck! contd. . .
Summer 2011 Final Examination CSC108 H1Y
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 19 / 6
Part (b) [1 mark]
print 12 - 4.0*3 + 2
Part (c) [1 mark]
z = 3 * "Blah"
print z + str(3) + "Blah"
Part (d) [1 mark]
ratio = 1.5433333
print "Ratio is %.4f", % (ratio)
Part (e) [1 mark]
s = "abc"
for c in s:
piece = ""
for i in range(4):
piece = c * i + ":"
print piece
Part (f) [1 mark]
s = "abc"
for i in range(2):
piece = ""
for c in s:
piece = piece + str(i) + c * i
print piece
Page 2 of 20 Student #: contd. . .
Each of the code sequences below runs without error. Show the output for each. The next page is provided
for your rough work.
Part (a) [2 marks]
morning = ["wake_up",["breakfast","drink"],"commute"]
afternoon = morning[:]
afternoon[2] = "work"
afternoon[1][0] = "lunch"
print morning
print afternoon
Part (b) [2 marks]
morning = ["wake_up",["breakfast","drink"],"commute"]
afternoon = morning
afternoon[2] = "work"
afternoon[1][0] = "lunch"
print morning
print afternoon
Part (c) [2 marks]
team = {1: "Anya", 23: "Yosuke", 34: ["Joseph"]}
new+team = {}
for key, value in team.items():
new_team[key] = value
new_team[44] = "Gilbert"
team[34].append("Sahar")
print team
print new_team
Part (d) [2 marks]
team = {1: "Anya", 23: "Yosuke", 34: ["Joseph"]}
new_team = team
new_team[44] = "Gilbert"
team[34].append("Sahar")
print team
print new_team
Use the space below for rough work. This page will not be marked.
8 1 6
3 5 7
4 9 2
Note that in the above magic square, each row, column and diagonal add to 15. We can use this to
create a very basic algorithm to play tic tac toe. Tic tac toe is a game in which 1 player plays Xs in a 3
by 3 grid, and the other player plays Os. Each player can draw their symbol in one square of the grid, and
when they do so the other player gets a turn. A player can only draw in empty squares. A player wins
when they can have 3 of their symbols on either a row, column or diagonal. The magic square allows us to
view this game dierently. Each player chooses a a number from 1 to 9, and the rst player that chooses
3 numbers that add exactly to 15 wins. When a player chooses a number, that number disappears.
An example of Tic tac toe were player 1 (the X player) wins:
X O
X X O
X O
Part (a) [5 marks]
Write the following function according to its docstring:
def win(my_nums):
Return True iff (list of ints) my_nums contains a set of 3 numbers that adds to 15.
Part (b) [7 marks]
Given a correct implementation of wins, write the following function according to its docstring:
def chose_num(my_nums, rem_nums):
Choose a number from (list of ints) rem_nums, remove that number
from rem_nums, add that number to the (list of ints) my_nums, and
return the number. If there is a number in rem_nums that can be added
to my_nums so that my_nums contains three numbers that add to 15,
then make sure that number is the one that is returned. Otherwise return
an arbitrary number.
Suppose you have a le rainfalls.txt that contains the rainfalls that occurred in a given town over the
last years. Each day is represented by a separate line, and the rainfall is given in the format 11mm where
11 can be replaced with any non-negative integer. Write code that will calculate the average amount of
rainfall over the last year, and store it in a variable rain_avg.
Suppose you have a dictionary sales_records where they keys are employee names, and the values are
lists whose elements are ints that represent the value of each individual sale made by an employee. Now,
suppose we want quick access to the biggest sale made by each employee. To do this we create a new
dictionary biggest_sales with the same keys, but whose values are ints that represent the biggest sale
made by that employee. If an employee has made no sales, his biggest sale is considered to have a value of
0.
Write code to generate biggest_sales
Suppose that we are keeping track of test data for test subjects, and we bring them in for tests once a
month. We dont want to keep our program consistently running, so we will use pickle to load our data.
Suppose we have our data stored in a le called data.pkl. In the pickle le we have a dictionary called
study_results where the keys are patient names, and the values are dictionaries where the keys are month
names and the values are test results. Assume that cpickle has been imported.
Write the following function according to its docstring:
def update_data(month, test_results):
Update study_results with the test results for the month
(str) month. test_results is a dictionary where the keys are patient
names, and the values are test results.
Consider the case when we want to have mutable strings. One way to do this, is replace strings with lists,
where every list element is a single character (that is, a one element string). Assume the following is a
module called mut_str.py
Part (a) [4 marks]
Replace the pass statements with code that matches the docstring.
def create_mut_string(string):
Given a regular string, return a list of individual characters that matches
the contents of the string.
pass
def mut_string_to_string(L):
Given a list of chars L, returns a string which matches the contents
of L.
pass
def is_mutable_string(L):
Return True iff the contents of L are that of a mutable string.
pass
Part (b) [7 marks]
Now say you wish to test your code using Nose: ll-in the following almost empty code of test__mut_str.py
with your own tests so that when we run it, nose runs your tests successfully..
import nose
if __name__ == "__main__":
nose.runmodule()
As we saw in class, sometimes we rst write psuedocode before writing real code. Consider the following
psuedocode for the following function foo, that takes a nested list L:
foo (L)
M=[]
for each sublist i in L:
append the maximum element in L[i] to M
return the median element of M.
Recall that the median means an element that has an equal number of elements above and below it.
Anotherway to think about the median is the middle element in a sorted list. (You can assume that L has
an odd number of sublists.)
Part (a) [5 marks]
Write python code to implement foo:
Part (b) [2 marks]
Write a docstring for foo:
Consider the following partially written class, that describes a painting. :
class Painting(object):
An oil painting, with a name, a painter_name, an owner, a list of past owners, and a value.
def __init__(self, name, painter):
A new painting with name s painted by the
painter, no owner (or past owners) and a value of 0.
self.name = name
self.painter = painter
#Complete this.
def get_value(self):
return self.value()
def add_owner(self, owner, value):
Add str owner as the owner of this painting, and add the old owner to the list if past owners.
Update the paintings value to the (int) value that the owner paid for it.
#Write Me.
Part (a) [2 marks] Finish writing the constuctor (the __init__ method).
Part (b) [3 marks] Finish writing the add_owner method.
Part (c) [2 marks] Create a Painting variable called p1. Its name is The Milkmaid and the painter
is Vermeer. Then call a method that represents what happens if John buys it for 100000000.
Part (d) [2 marks] Write the following new method, to be added to the class.
def num_past_owners(self):
Return the number of times the painting has been owned before.
Part (e) [4 marks] Write the __cmp__ method below, also to be added to the class. Dene it so that if
we call sort on a list of paintings, they will come out in order from cheapest (having the smallest value)
to most expensive (having the largest value).
def __cmp__(self, other):
Throughout this question, assume that we are sorting lists into non-desending order. Do not guess on
the yes/no questions. There is a one-mark deduction for incorrect answers.
Part (a) [2 marks]
We are partly through sorting a list, and have completed 3 passes through the data. That is, we have
called select 3 times. The list currently contains [-1, 12, 17, 18, 17, 33, 98, 17] Could we be
doing selection sort? Circle one.
yes no
Suppose it is insertion sort that we are doing. We have completed those 4 passes through, and the list
contains: [1, 64, 100, 110, 25, 234, 222, 109, 177] Show the state of the list after the next (5
th
)
pass through it.
Part (b) [2 marks]
We are partly through sorting a dierent list, and have completed 4 passes through the data. The list
currently contains [-10, 0, 22, 27, 34, 64, 33, 28, 33] Could we be doing insertion sort? Circle
one.
yes no
Suppose it is selection sort that we are doing. We have completed those 4 passes through, and the list
contains: [1, 25, 64, 100, 110, 234, 222, 109, 177] Show the state of the list after the next
(5
th
) pass through it.
Part (c) [2 marks]
We are partly through sorting a dierent list, and have completed 4 passes through the data. The list
currently contains [2, 9, 12,19 98,65,21,65,46,2] Could we be doing selection sort? Circle one.
yes no
Suppose it is bubble sort that we are doing. We have completed those 4 passes through, and the list
contains: [1, 23, 4, 56, 46, 45, 6, 65, 58, 70, 80, 90, 100] Show the state of the list after
the next (5
th
) pass through it.
Dont guess. There is a 1-mark deduction for wrong answers to parts (a) through (d).
Part (a) [2 marks]
def f1(s):
num_digits = 0
for c1 in s:
if c1.isdigit():
num_digits = num_digits + 1
return num_digits
Let n be the length of the string s passed to this function. Which of the following most accurately describes
how the runtime of this function grow as n grows? Circle one.
(a) It grows linearly, like n does. (b) It grows quadratically, like n
2
does.
(c) It grows less than linearly. (d) It grows more than quadratically.
Part (b) [2 marks]
def f2(n):
x = 0
while n > 0:
x = x + n * x
for i in range(800):
x = x + 1
n = n - 1
return x
Let n be the positive int passed to this function. Which of the following most accurately describes how
the runtime of this function grow as n grows? Circle one.
2
does.
Part (c) [2 marks]
def f3(s):
num = 0
for c1 in s:
for c2 in s:
if c1 != c2:
num = c1 - c2
return num
2
does.
Part (d) [2 marks]
def f4(s):
j=0
L = []
for i in range(len(s):
L.append[0]
while j < len(s):
L[j] = L[j] + 1
if L[j] == 3:
L[j] = 0
j = j + 1
else:
j = 0
2
does.
[Use the space below for rough work. This page will not be marked, unless you clearly indicate the part
of your work that you want us to mark.]
[Use the space below for rough work. This page will not be marked, unless you clearly indicate the part
of your work that you want us to mark.]
Short Python function/method descriptions:
__builtins__:
len(x) -> integer
Return the length of the list, tuple, dict, or string x.
max(L) -> value
Return the largest value in L.
cmp(x, y) -> integer
Return negative if x<y, zero if x==y, positive if x>y.
min(L) -> value
Return the smallest value in L.
open(name[, mode]) -> file object
Open a file. Legal modes are "r" (read), "w" (write), and "a" (append).
range([start], stop, [step]) -> list of integers
Return a list containing the integers starting with start and ending with
stop - 1 with step specifying the amount to increment (or decrement).
If start is not specified, the list starts at 0. If step is not specified,
the values are incremented by 1.
raw_input([prompt]) -> string
Read a string from standard input. The trailing newline is stripped.
cPickle:
dump(obj, file)
Write an object in pickle format to the given file.
load(file) --> object
Load a pickle from the given file
dict:
D[k] --> value
Return the value associated with the key k in D.
k in d --> boolean
Return True if k is a key in D and False otherwise.
D.get(k) -> value
Return D[k] if k in D, otherwise return None.
D.keys() -> list of keys
Return the keys of D.
D.values() -> list of values
Return the values associated with the keys of D.
D.items() -> list of (key, value) pairs
Return the (key, value) pairs of D, as 2-tuples.
file (also called a "reader"):
F.close()
Close the file.
F.read([size]) -> read at most size bytes, returned as a string.
If the size argument is negative or omitted, read until EOF (End
of File) is reached.
F.readline([size]) -> next line from the file, as a string. Retain newline.
A non-negative size argument limits the maximum number of bytes to return (an incomplete
line may be returned then). Return an empty string at EOF.
float:
float(x) -> floating point number
Convert a string or number to a floating point number, if possible.
int:
int(x) -> integer
Convert a string or number to an integer, if possible. A floating point
argument will be truncated towards zero.
list:
x in L --> boolean
Return True if x is in L and False otherwise.
L.append(x)
Append x to the end of the list L.
L.index(value) -> integer
Returns the lowest index of value in L.
L.insert(index, x)
Insert x at position index.
L.remove(value)
Removes the first occurrence of value from L.
L.reverse()
Reverse *IN PLACE*
L.sort()
Sorts the list in ascending order.
random:
randint(a, b)
Return random integer in range [a, b], including both end points.
str:
x in s --> boolean
Return True if x is in s and False otherwise.
str(x) -> string
Convert an object into its string representation, if possible.
S.count(sub[, start[, end]]) -> int
Return the number of non-overlapping occurrences of substring sub in
string S[start:end]. Optional arguments start and end are interpreted
as in slice notation.
S.find(sub[,i]) -> integer
Return the lowest index in S (starting at S[i], if i is given) where the
string sub is found or -1 if sub does not occur in S.
S.index(sub) -> integer
Like find but raises an exception if sub does not occur in S.
S.isdigit() -> boolean
Return True if all characters in S are digits and False otherwise.
S.lower() -> string
Return a copy of the string S converted to lowercase.
S.lstrip([chars]) -> string
Return a copy of the string S with leading whitespace removed.
If chars is given and not None, remove characters in chars instead.
S.replace(old, new) -> string
Return a copy of string S with all occurrences of the string old replaced
with the string new.
S.rstrip([chars]) -> string
Return a copy of the string S with trailing whitespace removed.
If chars is given and not None, remove characters in chars instead.
S.split([sep]) -> list of strings
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() -> string
Return a copy of S with leading and trailing whitespace removed.
S.upper() -> string
Return a copy of the string S converted to uppercase.
Total Marks = 88
Page 20 of 20 Student #: End of Final Examination

CSC108 Final 2011S

Uploaded by

Copyright:

Available Formats

CSC108 Final 2011S

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CSC108 Final 2011S

Uploaded by

Copyright:

Available Formats

P

You might also like