Midterm2 Practice
Here are some practice problems for you!
More Midterm2 Practice
These problems were designed by CA's to help you study for midterm2. They
may or may not represent the actual materials on the exam, but in any case they
surely are topics you should understand! Enjoy!
Andre:
1) What does this code print?
def f(x):
if not x:
return [x]
else:
y = []
for k in range(len(x)):
z = x[:k] + x[k+1:]
for m in f(z):
y.append(x[k:k+1] + m)
return y
print f('koz')
2) What does this code print?
def f(a,n):
if a[0]<=a[len(a)-1]:
a[0]+=a[a[n]%len(a)]
f(a,(2+n)%len(a))
a = [2,3,4,15,25,35]
print a, f(a,0)
Margaret:
3) In just a few words of English what does the following function do?
def mystery(a,b):
return (type(a)==str) and (len(a)>0) and\
(a[0]==b or mystery(a[1:], b))
4) Find inputs a and d such that f(a, d) returns True
def f(a, d):
assert(type(a)==set)
assert(len(a)==3)
for x in a:
assert (x in range(5))
count = 0
for key in d:
if (d[key]==x):
count+=1
assert(count==x)
return True
Jordan:
5)
#in a few words, what does this do?
def f(a):
#a is a list of numbers
def s(b):
l = len(b) / 2
return b[:l], b[l:]
def g(b):
if(len(b) == 1):
return b[0]
else:
return min(g(s(b)[0]), g(s(b)[1]))
def h(b):
if(len(b) == 1):
return b[0]
else:
return max(h(s(b)[0]), h(s(b)[1]))
if(len(a) == 0):
return None
elif(len(a) == 1):
return a[0]
elif(len(a) == 2):
return (a[0] + a[1]) / 2.0
else:
a.remove(g(a))
a.remove(h(a))
return f(a)
6) #what input returns true?
def f(a):
def g(b, m):
result = True
for c in b:
if type(c) == list:
result = result and g(c, 1 - m)
else:
result = result and c % 2 == m
return result
assert(len(a) == 2)
assert(type(a[1]) == list and len(a[1]) == 2)
assert(type(a[1][1]) == list and len(a[1][1]) == 2)
assert(g(a, 0))
Akash:
7) Very short answer: Why is it a good idea to have large number of buckets than a small numbers for a set/dictionary?
8) In a few words of English what does this function do?
def mysteryA(l):
if len(l)<=1:
return True
else:
return (l[0] == l[-1]) and mysteryA(l[1:len(l)-1])
Michael C:
9) Write a function filter(a, f) that takes in a list a and function f,
and returns a list of the elements x in a for which f(x) returned true.
Your function should be both recursive and nondestructive.
10) Write selection sort. Your function should be destructive.
11) write a function getNameMap(a), that takes in a square 2-d list of names
and returns a dictionary mapping every name to its average location in the grid.
For example, getNameMap([["Alan", "Alan"],["Bob", "Keith"]]) would return
"Alan" -> (0.5, 0)
"Bob" -> (1, 0)
"Keith" -> (1, 1)
12) BONUS: what does this do, as plainly and simply as possible?
def magic1(n):
assert (n >= 0)
if (n == 0): return 1
if (n == 1): return 2
return magic1(n-1) * magic2(n - 2)
Connor:
13) Physics Simulator: Use TKinter to build an environment where a user can click to draw circles. Once circles are drawn, they should begin accelerating towards the bottom of the screen will an acceleration of 10 pixels/timestep**2. When circles collide with the bottom/sides of the screen, they should bounce off (do this by maintaining two velocities, dx and dy, and multiplying the relevant velocity by -1 whenever a collision occurs). Remember that acceleration is defined as change in velocity over time (so a good way to make the circles accelerate would be to add 10 to their velocities every timestep).
14) Ordered List: Define a class OrderedList that allows users to insert and remove integers and always stays sorted from low to high. You should define the following methods:
__init__
insert(number)
remove(number, number_of_instances_to_remove)
__str__
Leon:
15) # In 10 words or less, explain what this function does.
def foo(s):
assert type(s) == str
if len(s) <= 1:
return True
else:
return s[0].lower() == s[-1].lower() and foo(s[1:-1])
16) # In 15 words or less, explain what this function does.
def bar(x):
assert type(x) == int
assert x >= 0
z = 0
d = {0: 0}
while x > 0:
y = x%10
d[y] = d.get(y, 0) + 1
# hint: these conditions are split for a reason...
if d[y] > d[z]:
z = y
elif d[y] == d[z] and y > z:
z = y
x /= 10
return z
Amelia:
17) Free Response:
Assuming class Person(object) is already written and that every Person has a first name and a hometown, write a function that takes a list of Person objects and returns a dictionary mapping hometowns to the set of people who live in them for the given list.
for example:
personList = [Person("harold", "Philly"), Person("jim", "New York"), Person("alice", "New York"),
Person("joe", "Chicago"), Person("samantha", "Philly")]
HomeTowns(personList) would return the dictionary {'New York': set(['jim', 'alice']), 'Philly': set(['samantha', 'harold']), 'Chicago': set(['joe'])}
18) Find values for x, y, z such that the following function returns true.
def f(x,y,z):
if len(str(x)) == 1:
return x
else:
n = f(x/10, y, z+1) + x%10
if z != 0:
return n
else:
return n == y
Veronica:
19)What will this code print?
class Account(object):
mainAccountFunds = 0
allAccounts = []
def __init__(self, title, amount):
self.funds = amount
self.title = title
Account.allAccounts.append(self)
Account.mainAccountFunds -= amount
@classmethod
def deposit(klass, amount):
Account.mainAccountFunds += amount
@classmethod
def withdraw(klass, amount):
Account.mainAccountFunds += amount
@classmethod
def showAllAccounts(klass):
print "\nAll Accounts:"
for account in Account.allAccounts:
print "\t%s:\t\t%s" %(account.title, str(account.funds))
print "Leftover: %s" %(Account.mainAccountFunds)
def transfer(self, amount):
self.funds += amount
Account.mainAccountFunds -= amount
def __str__(self):
return (self.title, self.funds)
Account.deposit(5000)
checking = Account("checking", 2000)
savings = Account("savings", 1000)
Account.withdraw(500)
savings.transfer(-200)
Account.showAllAccounts() # What does this print?
20) def foo(n):
if n < 0:
print 0,
else:
foo(n-2)
foo(n-3)
print 0,
foo(5) #how many zeroes are printed?
Charlie:
21) #describe in a few words what the follwoing function does:
def f(a,g):
if (len(a) < 2):
return a
else:
b = f(a[1:], g)
i = 0
while (i < len(b) and g(a[0],b[i]) > 0):
i += 1
return b[:i] + [a[0]] + b[i:]
22) #provide an a such that f2 returns true
def f2(a):
assert(len(a) == 5)
d = dict()
for i in xrange(len(a)):
d[a[i]] = i
return (d == {"a": 3, "b": 2, "c":4})
23) #provide an x, y such that f3 returns true
def f3(x,y):
(a,b) = x,y
while (0 not in (a,b)):
if (a > b):
(a,b) = (a%b, b)
else:
(a,b) = (a, b%a)
return (a == 5 or b == 5)
Michael O:
24) find an a such that f(a) returns true
def f(a):
assert(type(a) == list)
b = [2*i for i in xrange(20) if i % 5 == 0]
c = range(0,100,2)
d = [a[i]+c[i] for i in xrange(len(a))]
return d == b
25) Find x, y, z such that g(x,y,z) returns true
def g(x,y,z):
t = x
if (y % 8 != 1): return False
while True:
if (z % 7 == 0):
break
d = z % 8
#print d
if (d != 0 and z != 1):
return False
x += z
z /= 8
return x == y and t+100 < y
Justin:
26) # What does the code print?
def g(x, y):
if (x <= 0):
return y
else:
return g(x-1, y+2) + 3*g(x-2, y+1)
def f(x,y):
return g(x, y) + g(y, x)
print f(2,3)
27) # Write what the code does in one sentence.
def s(x,y):
return x + y
def h(s, b, L):
if (len(L) == 0):
return b
else:
return h(s, s(b,L[0]), L[1:])
print h(s, 0, [1,2,3])
Shikun:
28) Find a value for l such that f(l) returns true
def f(l):
x = len(l)/3
s1 = l[0:x]
s2 = l[x:2*x]
s3 = l[2*x:]
return g(s1, s2, s3) == range(10)
def g(l1, l2, l3):
if (len(l1) == 0 or len(l2) == 0 or len(l3) == 0):
return l1 + l2 + l3
else:
return [l1[0], l2[0], l3[0]] + g(l1[1:], l2[1:], l3[1:])
29) Write in a few words of English what the following code does.
def f2(l):
for i in range(len(l), 0, -1):
l = g2(l, i)
return l
def g2(l, j):
for i in xrange(1,j):
if l[i-1] > l[i] :
(l[i], l[i-1]) = (l[i-1], l[i])
return l
Dan B:
30) Define a Color class that has the following methods and properties:
Properties:
red (0 to 255)
green (0 to 255)
blue (0 to 255)
31) Write the following methods for the Color class:
toRGBString: this method returns a string representing the Color, taking the form "#RRGGBB", where RR is the color's red value in hexadecimal format (aka 255 = 0xff), and so on. Note that the string must always be 7 characters long.
fromRGBString(rgbs): this method takes an RGB string, formatted like above, and sets the red, green, and blue properties of the color instance to those values.
inverse: this method produces a new Color instance with the opposite values for red, green, and blue (ie 255-red, etc)
Edison:
32) Describe in a few words what the following code does. (We’ve seen the algorithm in class/recitation before)
def f1(n):
assert(type(n) == int)
def g(l):
if l == []: return []
else:
x = l[0]
rest = [i for i in l if (i%x != 0)]
return [x] + g(rest)
return g(range(2,n))
33) What does the following code print? Describe in a few words what the function f2 does
def f2(l,n):
assert(type(n) == int)
#l is a list of integers
if l == []:
return True if n == 0 else False
else:
x = l[0]
return f2(l[1:],n) or f2(l[1:],n-x)
print f2([1,2,3,4],-1)
print f2([1,2,3,4],10)
print f2([2,3,5,-1], 6)
Dan C:
34) In just a few words, what does this code do?
def f1(a):
#assume a is a list
if not len(a) or not len(a) - 1:
return a
else:
b = f1(a[1:])
for i in xrange(len(b)):
if a[0] < b[i]:
return f1(b[:i])+[a[0]]+f1(b[i:])
return f1(b) + [a[0]]
35) In just a few words, what does this code do?
def f2(n):
#assume n is a positive int
if not n: return True
elif n <= 2: return False
else:
return f2(n / 10 + n % 3)
Brian:
36) What will the following print?
class Foo(object):
a = "hello"
b = "hola"
@classmethod
def getA(cls):
return cls.a
class Bar(Foo):
a = "goodbye"
print Foo.getA()
print Bar.getA()
print Foo.b
print Bar.b
37) What input to f will return True? Hint: figure out what f does on small inputs first.
def f(a):
if a == []:
return []
b = f(a[1:])
if a[0] % 2 == 0:
return [a[0]] + b
else:
return b + [a[0]]
38) What will the following print? What's the worst-case runtime in terms of big-O and what kind of list would cause that?
def g(a, i=0):
if i + 1 >= len(a):
return
else:
g(a, i+1)
if a[i] > a[i+1]:
a[i], a[i+1] = a[i+1], a[i] # swap a[i] and a[i+1]
g(a, i+1)
a = [10, 13, 5, 15, 7, 19, 3, 12, 8, 18]
g(a)
print a
Stuart:
39) What will the following print?
class A(object):
def __init__(self, a):
self.a = f(a)
def f(self):
return 'c'.join(self.a)
def f(*args):
if len(args) == 1:
return args[0].split("_")
else:
return "_".join(args)
a = ('a', 'b', '_')
print f(f(*a), A(f(*a)).f())
40) def fib(n):
if n == 1 or n == 0:
return 1
else:
return fib(n-1) + fib(n-2)
#Name a case when this will recurse forever, and suggest a way to fix it.
DJ:
41) What does the following print?
class A(object):
def __init__(self, x, y):
self.x = x
self.y = y
def __str__(self):
return "x=%d, y=%d", %(self.x,self.y)
def __eq__(self, other):
return other.y == self.y
def __hash__(self):
return hash(self.y)
d = {A(1,2):"a",A(3,1):"b",A(3,3):"c",A(1,1):"d" }
try:
print d[A(3,3)]
print d[A(1,2)]
print d[A(5,2)]
except:
print "caught exception"
Mark:
42) In this problem we will work with an abstract concept
called a BTree. A
BTree is
either empty OR it has a piece of data, and a left and a right BTree. Your
task
is to write a class to represent Tree objects. The following are example
invocations to the BTree's constructor.
BTree() gives the empty BTree
BTree(BTree(), 3, BTree()) gives the BTree that consists of only one piece of
data, which is the number three.
BTree(BTree(BTree(), 4, BTree()), 3, BTree(BTree(), 6, BTree(BTree(), 7,
BTree())))
gives the following BTree:
3
/ \
4 6
\
7
(a) Write the constructor for BTree. Hint: you might want to use default
argument.
How are we going to compare whether two BTrees are equal? Well, given two
BTrees, if they are both empty then they are equal. Otherwise, if they are
both
not empty, then we need to check that their data are equal, and their left
BTrees are equal, and their right BTrees are equal. Otherwise, we deem
them to
be not equal.
(b) Write the __eq__ function for the Tree class.
(c) Write the __repr__ function for the Tree class, such that if bt is a
BTree, eval(repr(bt)) == bt.
A BSTree is a BTree with the following properties: if BTree is empty then
it is a BSTree. Otherwise, if BTree is non-empty then all the data in its
left
BTree needs to be less than or equal to the data it contains, and all the
data
in its right BTree needs to be greater or equal to the data it contains. For
example.
(d) Write the method isBSTree which takes in an argument, and if it is a
BTree, checks whether it is a BSTree. For example,
BTree.isBSTree(BTree()) returns True
BTree.isBSTree(BTree(BTree(), 3, BTree())) returns True
BTree.isBSTree(BTree(BTree(BTree(), 4, BTree()), 3, BTree(BTree(), 6,
BTree(BTree(), 7, BTree())))) returns False, because four is in the left
BTree
but is greater than three.
AJ:
43) In plain English, explain what the following expression evaluates to. You may
assume that a list, with elements such that the evaluation won't crash.
Bonus: name the algorithm.
Bonus Bonus: find a shorter expression for this algorithm.
a if len(a) == 0 else s([x for x in a[1:] if x < a[0]]) + \
[a[0]] + s([x for x in a[1:] if x >= a[0]])
44) In plain English, explain what function c does.
class N(object):
def __init__(self, d, n):
assert(type(d) == int and (n == None or isinstance(n, N)))
self.d = d
self.n = n
def c(self):
def cc(this, that):
if that == None or that.n == None:
return False
if this == that:
return True
# not that the following expression is recursive
# and pay special attention to each term
return cc(this.n, that.n.n)
return cc(self, self.n)
Even More Midterm2 Practice
These problems were designed by CA's to help you study for midterm2. They
may or may not represent the actual materials on the exam, but in any case they
surely are topics you should understand! Enjoy!
Towers of Hanoi Animation
Check this out: hanoiAnmation.py
You should understand how this works in every regard!
Set-Example
Check this out: set-example.py
You should understand how this works in every regard!
Sets + Dictionaries
1. Understanding dictionaries
a. Why can’t I use a list as a key in a dictionary? Be specific.
b. Why is lookup time faster in a dictionary than it is in a list?
2. Write the function containsAllLetters(s), which takes in a string s, and returns True if that string contains all the letters in the alphabet, and False otherwise. For example, containsAllLetters(“hi there, I like ponies”) returns false, but containsAllLetters(“the quick brown fox jumps over the lazy dog”) returns True.
3. Give an input that returns true (there are many; give one).
def foo(s):
assert(len(s)==15)
assert("blarg" in s)
a=[s[i] for i in xrange(0,len(s),2)]
b=set(["a","b","c"])
for elem in a:
b.add(elem)
assert(len(b)==7)
return True
4. Fix this code so it will run (correctly). It should count the number of each letter in a given string and return a dictionary (keys are letters, number of letters are values) with the correct values.
def countLetters(string):
d=dict()
for c in string:
d[c]+=1
return d
5. Write makeDictionary(wordList) which takes a wordList (which is a SET of words, like 'set(["foo”,"bar","huzzah"])') and puts them in a dictionary based on their first letter. So "apple" would go into the dictionary under "a". There should be a key in the resulting dictionary for all 26 letters in the alphabet. Each key should have either the value None (if there are no words starting with that better) or a SORTED list of words beginning with that letter.
##############################################################################
Classes
1. Here is a struct representing a classroom.
def CAsNeeded(classRoom):
return classRoom.studentCount / 25
def getCAs(classRoom):
return classRoom.CAs
def printInfo(classRoom):
print “Professor “, classRoom.professor
print classRoom.studentCount, “ students”
print CAsNeeded(classRoom), “CAs: “, classRoom.CAs
class Struct: pass
classRoom = Struct()
classRoom.studentCount = 241
classRoom.professor = “Kosbie”
classRoom.CAs = [“Michael”,”Yuyang”,”Maddy”,”Ashley”,”Charlie”,”Alex”, “Tamar”, “Andre”, “Jordan”]
Write a class called ClassRoom which represents the same information.
2. Write the __eq__ function such that two classRooms with similar properties will evaluate to be the same thing.
3. Explain the difference between the functions __str__ and __repr__. Give an example of something that you might try to print that would cause str to fail (or rather, give undesirably output) and yet repr would work perfectly.
4. Use the following classes:
class School(object):
def __init__(self, name):
self.name = name
def nameOf(self):
return self.name
def typeOf(self):
return "public"
class HighSchool(School):
def __init__(self, name):
super(HighSchool, self).__init__(name)
self.name += " High School"
class HighSchool(School):
def __init__(self, name):
super(HighSchool, self).__init__(name)
self.name += " High School"
class PrivateSchool(School):
def __init__(self, name):
super(PrivateSchool, self).__init__(name)
def typeOf(self):
return "private"
Given the code below, what are the least amount of calls needed that would return all the possible strings that can be returned? (list the calls)
school1 = School("Martin")
school2 = HighSchool("Martin")
school3 = PrivateSchool("Martin")
5. What are the relationships (if any) between the 3 classes above?
6. If you added a uniformType() function to the PrivateSchool class, what would happen if you did the following?
print school1.unformType()
print school2.uniformType()
print school3.uniformType()
##############################################################################
Graphics + Animation
1. Draw a ball moving across the screen that 1) changes color when you press “c”, 2) switches direction when you press “r”, and 3) stops when you press the left and right arrow keys at the same time.
2. true or false : you should have drawing commands in timerfired
3. in a 200 x 200 pixel window, draw what canvas.create_text(150, 100, text="Carpe Diem!", anchor=NW, fill="orange", font="Times 18 italic") would look like assuming all the necessary graphics functions like timerfired are there.
##############################################################################
Recursion
1. In English describe what the following code does
def mys(a):
assert(isinstance(a,list))
if len(a) < 2 :
return a
else:
mid = len(a) / 2
left = mys(a[:mid])
right = mys(a[mid:])
i,j = 0,0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]) i+=1
else:
result.append(right[j]) j+=1
result += left[i:]
result += right[j:]
return result
2.
Suppose we modify our floodFill like this
def floodFill(row, col, color, depth):
if (same condition...):
return
else:
floodFill(row-1, col-1, color, depth+1)
floodFill(row-1, col+1, color, depth+1)
floodFill(row+1, col-1, color, depth+1)
floodFill(row+1, col+1, color, depth+1)
label the cells with numbers indicating the DEPTH when the cells are filled
(starting with 0)
3. Memoization and Recursion Depth
According to the way we wrote fib in class
(a) without memoize, how many times fib(1) is called if we do fib(4)? what are their depths? how many fib(something) did we call in total?
(b) with memoize, how many times fib(1) is called if we do fib(100)?
(c) what would happen if we call fib(1000)? How can we fix it?
4. def f(n):
return [] if n<=0 else [f(i) for i in xrange(n)]
f(3) = ?
hint: you might consider memoizing your results as you trace this one :)
5. write map(a,f), which takes in a list a and a function f, and applies f to every element in a.
For example: map([x1,x2,x3],f) = [f(x1),f(x2),f(x3)]
6. write filter(a,f), which takes in a list and a function f, and gives back only the elements x in a for which f(x) = True.
For example: filter([0,1,2,3,4,5],isEven) = [0,2,4]
7. Write a function evenDirs(path), which takes in a path to a directory, and returns a list of all the directories in path (possibly including itself) which contain an even number of files (and any number of folders). Note that 0 is an even number!
8. Write a function getPathDict(path), which takes in a path to a directory, and returns a dictionary that maps all the file names in the directory to their complete paths. For example, if path = “C:\folderA”, and inside folderA is a folder folderB which contains wahoo.txt, then getPathDict(path)[“wahoo.txt”] = “C:\folderA\folderB\wahoo.txt”. You are not responsible for what it does if there are multiple files with the same name living in different folders!
9. Write the funciton subsetSum(a,n), which takes in a list a of integers (might be negative!), and a number n, and returns true if and only if there’s a sublist of the numbers in a that sums to n. For example:
subsetSum([1,2],1) = subsetSum([1,2],3) = subsetSum([1,2],0) = True (the empty list is a sublist!)
subsetSum([1,2],-1) = subsetSum([1,2],4) = False.
##############################################################################
Monte Carlo
1.Use a Monte Carlo method to predict the probability of getting a blackjack with just 2 cards taken from a deck of poker cards. (The 2 cards must sum to 21)
2. Use a Monte Carlo method to predict the probability of getting a Yahtzee in a game of Yahtzee (getting 5 dice with the same values). The function should take 1 input which is the number of sides of the dice (Yes, dice do not only come six sided).
3. Use a Monte Carlo method to estimate the area under the curve of y = x^2 + 1 for x between 0 to 5 inclusive.