These materials were created by CA's to help you study for the final exam. Enjoy, and good luck on the final!
Operators and Expressions
1) decide what the following code would print
4+1<<2
round(4.9)
int(4.9)
math.ceil(4.9)
4^10
0x15112CA & 0xbeef
bin(45)
eval( repr([ ‘hola~’, (‘beef’,), “pork”, 3.14159, yuyangIsHungry’]))
float(4/3)
if not “” : print “haha!Gotcha!” (what if we substitute “” with [], or ()...)
0.1+0.1+0.1 == 0.3 (tricky one~!)
True of false: for any integer x, and non-zero integer y, it is true that x/y + x%y == x
2) which of the following is an operation? which is an expression? which is neither?
a) a = 3.1415926
b) a*3.1415926
c) if (a == 3.1415926): print a
3) write a function without conditionals that does the following:
implement myOrd() that takes in only an upper or lower letter and returns a numeric representation of each character. The mapping is as the following
“a”, “b” => 1
“c”, “d” => 2
“e”, “f” => 3
“g”, “h” =>1
“i”, “j” =>2
“k”, “l” =>3
…...
“w”, “x” => 3
“y”, “z” => 1
e.g. myOrd(“a”) should return 1, myOrd(“w”) should return 3
4) suppose our pixel is encoded with RGBA in the format 0xRRGGBBAA, write one line using bitwise operators to extract the green value. (use p as the pixel value)
5) (this would require some knowlegde of 2’s compliment, which is not a required topic, but you should definitely know there is a difference between int and long) With a 32 bit computer, decide what will the code print
print type(2**32)
print type(2**31)
print type(2**31-1)
print type(2147483647)
(given that the numeric value of 2**31-1 is 2147483647)
Monte Carlo Questions
Write a function:
You have a six-sided die whose sides are: “Diem”, “sin(b)/tan(b)”, “Carpe”, “42”, “15-112”, “!”. Write a function that uses Monte Carlo methods to return the probability of rolling the die three times and getting the concatenated result “Carpe Diem!”.
Approximate the probability that three randomly sized lines can produce a triangle where one of the angles is at least 90 degrees using Monte Carlo methods.
Assume that there are a collection of colored balls in a bag. There are r-many red balls, g-many green balls, and b-many blue balls. Employ Monte Carlo methods and write a function that takes in - as arguments - the number of r, g, and b balls in the bag and approximate the probability that a user chooses three blue balls in a row (without replacement). So if there were 5 red balls, 2 green balls, and 4 blue balls and the user picked a blue ball, there would now be 5-2-3 balls in the bag respectively. Note: If there are fewer than three blue balls, your function should return 0.
loops and conditionals
loops:
1) What will be the runtime of/what will it return:
def foo(n):
i = 0
for k in xrange(n):
for j in xrange(n/10):
i += 1
n /= 10
return i
2)What will be the runtime of / what will it print
def foo2(n):
i = 0
try: n = n/i
except : n = 7
for j in xrange (2,n+1):
i += 2
print [0]*i
return i
3) what will the following print:
for i in xrange(4,2,-1):
for j in xrange(1,6,2):
print i,j
for k in xrange(4,2):
print i*j+k
4) What will the following print:
i =5
for j in xrange(12):
while (true):
i += 1
if (i % 9):
break
i + = 2
print i
5) Explain the difference between xrange and range, and why we usually use xrange.
Lists and strings
1) make a (3*7) 2d list filled with 0s with one reasonable line of code
2) what will the following print (or say if it will crash):
a) [0]*2.4
b) [0]*3
c) [[“hi”]] *2
3) what will the following fragment print:
def foo(a):
for i in xrange(len(a)):
a[i] += 2
b = a.pop()
return a,b
a = [1,2,3,4,5]
print foo(a)
print a
4) what will the following print:
for j in xrange (1,5):
print “%s my\n name is”(“hello”)
5) a) reverse the string “helloThere” in one line
b) MAkeThisSEntencEAllLOwerCaSE (in one line)
6) what will the following print:
a = “123456789”
for j in xrange(4,1,-1):
if (i%2):
print a[i]
else: pass
Dictionaries and Sets
1. Write a function uniqueLetterCount that takes a String and returns the number of unique letters, ignoring case, that occur in that String. For example, "Wowee" contains the letters 'e', 'o', and 'w' (ignoring case), so uniqueLetterCount("Wowee") should return 3. Ignore all non-letters. The null string contains no unique letters. (Hint: the use of sets might be useful =D)
2. Sets cannot be used as a key in a dictionary. If you try using set as a key in a dictionary, an error saying: (unhashable type: 'set') will appear. Explain what this means and why a set is “unhashable”!
3. What does this print:
print [[1,[2,3],4],5][0:3][1]
print [1,{1:2},{1:3}][1:3][1][1]
print [1*3,'1'*3,{1:3},[1]*3][3][1]
print {1:['x','y'],7:'hey',9:1}[1][1]+'ou'
print {'hey':'won','I':'got','do':'it'}[{'I':'hey','you':'do'}['I']]
4. What are the differences between writing classes, using dictionaries and using Structs?
5. Write the function reverseGet(d, v) that takes a dictionary and a value, and returns either a key that is mapped to the given value in the dictionary, or None if no such key exists. For example, reverseGet([{"Steelers": 14, "Browns": 3}], 14) would return "Steelers", and reverseGet([{"Steelers": 14, "Browns": 3}], 10) would return None.
6. Write a recursive function fib(n) that returns the nth Fibonacci number. Note that when n is equal to 0 or 1, Fib(n) = 1. Then using what you know about dictionaries (and NOT @memoized), write a memoized function memoizedFib(n). Make sure to also store intermediate values! In other words calling memoizedFib(10) also allows memoizedFib(5) to be solved immediately.
7. What does this mystery function do?
d1 = { 0:0, 1:3, 2:7, 4:6, 5:3 }
def mystery1(d)
s = 0
c = 0
for n in d:
s += n*d[n]
c += d[n]
return 1.0*s/c
print mystery1(d1)
Recursion (normal)
Note: these are not arranged in any particular order :)
1. Write a function “uninterleave(a)”, which takes a list of integers [a,b,c,d,...] and outputs a tuple of the two lists ([a,c,e,...], [b,d,f,...]). Your function cannot use loops, or any builtin function other than len() (things like +,*,indexing don’t count, so you can still use them!).
2. Write a function “hanoiMoves(n, from, to, via)” that returns a list of all the moves (in order!) required to solve that specific instance of hanoi.
3. Write a function “countLeavingMoves(n)” that takes in no optional paramaters, and returns the number of moves from the starting post to another post that occur in a solution to hanoi(n). Note: there is an easy, less efficient way to do this, and a harder, more efficient way. You should write both!
4. write the function “countOnlyChildren(path)”, which takes in a path to a directory, and returns the number of files and (folders) in that directory which have no other files or folders in the same directory as them. (a child of a folder is something in that folder, so an only child is the only thing in it’s parent folder).
5. Consider the following function:
#takes in a nonnegative integer
def familiar(n):
if (n==0): return 1
elif (n==1): return 2
else:
return familiar(n-1)*familiar(n-2)
What is familiar(4)?
More interestingly, is there a nice (closed-form) way to express familiar(n)?
6. What does this print?
#takes in a nonnegative integer
def sNum(n):
if (n==0): return []
else:
return [sNum(i) for i in xrange(n)]
print sNum(3)
Recursion (bonus)
These quesitons are (I think) cool, but outside the scope of what you would be asked to reproduce on an exam. Be warned!
7. If you’re familiar with determinants of matricies, you may remember the method where you, for everything in a row, cross out a row and column, calculate the determinant of the rest, multiply it by the thing you crossed out, and do an alternating sum to get the determinant. If not (and you’re interested for some reason), here’s a somewhat dry explanation:
http://www.youtube.com/watch?v=louFpVlOhK8&feature=related
Now, write a function det(m), which takes in a 2D list, known to represent an n-by-n matrix, and calculates its determinant according to the above method.
8. Write the function get rankFolders(path), which takes in a path to a directory, and returns a list of all the folder names (not paths) in that directory (including itself), sorted from small to large by which ones have the most files as immediate children. So, if folder1 has one file in it and folder2, which has 2 files in it, the result is [folder1,folder2]. This one has a fair number of parts; I would use helper functions for this, and almost certainly one of them will be a wrapper :)
Graphics and Animation
1. What is incorrect about the following code? It is supposed to put a circle of radius 5 wherever the use clicks. (Hint: Think carefully)
def mousePressed(event):
x,y=event.x,event.y
r=5
canvas.create_oval(x-r,y-r,x+r,y+r,width=0,fill="red")
def init():
pass
def run():
#normal run function
2. Write a function drawFlag(colors,dir) that takes two arguments: a list of colours (as strings) and a string that is guaranteed to be either "Horizontal" or "Vertical". The function will then draw a 800x600 flag that has stripes of equal size in the direction of dir that are the colours listed in colors. So drawFlag(["black","red","gold"],"Horizontal") will draw the German flag.
3. Write an animation that creates a canvas that is 400x400, draws a circle in the center of the screen that is initially stationary. Once the user presses "p" the ball will ACCELERATE to the right at 1 pixel per second per second until it is moving at 20 pixels per second, at which point it decelerates at the same rate until coming to a stop, at which point it will begin the animation again. If the user presses "p" at any point, the animation pauses, and pressing "p" again will resume the animation where it left off. When the ball reaches the edge of the screen, it wraps around.
Note that for this problem, when it is said "per second", it really means per tick of timerFired. So when the change of the ball's X location applied every timerFired is 20, it should start slowing down. Also, remember that acceleration is just change in velocity, so adding 1 to the change in X applied every timerFired will accelerate the ball by 1 pixel per second per second (and -1 will decelerate it).
4. Write a program that initially starts out with a blank canvas. When the user clicks on the canvas, a circle is drawn at the location. If more than 2 circles are on the screen, a line should be drawn between the circles connecting circles in the order they were created. If the user presses the left arrow, the oldest circle should be deleted. If the user presses the right arrow, the newest circle should be deleted. Be sure to adhere to Model-View-Controller!
5. Write out the 2-D list that corresponds to the line piece and the L-block (either way) in Tetris.
6. Write findHead from Snake (as implemented in class).
7. Jordan was working on a lunarLander and noticed that if he held down the up arrow key, the ship’s fuel (indicating the ship's engines) would go down a little at first, not go down, and then start shooting down really fast. He wanted the fuel to go down at a smooth rate whenever the arrow key was held (since this is what his CAs told him it should do). After working on it for hours, he threw his arms up in the air and yelled "Was zum Teufel?!? Das ist blöd!" (What the heck?!? This is stupid!). Luckily, you know why his program is behaving incorrectly. Calmly explain to him how to fix his problem with key events before he disrupts the whole cluster with his German ranting.
Classes
What will the following code print?
class _15112(object):
def __init__(self, x, y):
self.x = x
self.y = y
def __add__(self, other):
other.x = other.x + 1
other.y = other.y + 1
return other
def __str__(self):
return "%d %x" % (self.x, self.y)
class _112Student(_15112):
def __init__(self, x):
super(_112Student, self).__init__(x, 2)
def __str__(self):
return "give me an %X?" % (self.x)
class CA(_15112):
def __init__(self, y):
super(CA, self).__init__(24, y)
def __add__(self, other):
return _112Student(other.x - 2)
def __str__(self):
return "I can help %d/%d" % (self.x, self.y)
a = _15112(112, 793173) #hint: hex(793168) == '0xc1a50', (note difference!)
b = _112Student(11)
c = CA(7)
print b
print a
print a + b
print c
print c + b
print “yes we can!”
#on an unrelated note:
print isinstance(b, _15112)
print isinstance(a, _112Student)
print isinstance(b, CA)
print isinstance(c, _112Student)
print isinstance(c, _15112)
class Foo(object):
big = None
def __init__(self, n, xFactor):
self.n = n
self.xFactor = xFactor
if (self > Foo.big):
Foo.big = self
def __gt__(self, other):
if (other == None): return True
return self.xFactor > other.xFactor
def __repr__(self):
return "Foo(%d, %d)" % (self.n, self.xFactor)
@classmethod
def biggestFoo(self):
return Foo.big
for i in xrange(5):
newFoo = Foo(i, 4 - i)
print Foo.biggestFoo()
What are all the classes we used in our partial text adventure? Which ones inherit from which other ones?
Name six of the double underscore (__XXX__) methods that we overwrote in our implementation of fractions. For each one, state the purpose of it. (Note: the __coerce__ method was actually unnecessary, see the python documentation for why)
when it comes to classes, what’s the difference between the type() function and the isinstance() function?
Why would you want to override the __hash__ function? What does that enable us to do?
Use classes to make an animation where two bubbles initially appear on the screen, with a random color (either blue, red, or green), moving random directions. If the user presses “b”, a new bubble should appear in a similar way. If two bubbles collide, they should pop and disappear. If a bubble would go off the edge, it should wrap around instead.
Big O
1. What are the runtimes of isPrime(n) and fasterInPrime(n) from the course notes?
2. What is the runtime of mergesort? Why?
def f1():
n = 100000
sum =0
for i in xrange(n):
sum += i
return sum
def f2(n)
for i in xrange(n**2):
for j in xrange(n):
if (i == j**2):
return True
return False
def f3(n):
sum = 0
for i in xrange(n/2):
sum += i**2
return sum
def f4(n):
if n <= 0:
return f1()
else:
return f4(n-1) + f4(n-2)
def f5(n):
i = 0
while (i < n):
f3(i)
i += 1
return i
3. What are the runtimes of f1(), f2(n), f3(n), f4(n), and f5(n)?