Midterm 2 practice questions

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

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)?

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.