15-112 Spring 2013 Midterm 2

* 80 Minutes.
* No calculators, no notes, no books, no computers.
* Show your work, circle your answers.

1.       [5 pts; 1 pt each] True or False (circle one):

a.    TRUE or FALSE:  Anything computed with recursion can also be computed without recursion.

b.   TRUE or FALSE:  In our version of Model-View-Controller animations, we stored our model in canvas.data, and we called various canvas methods in our view.

c.    TRUE or FALSE:  If we changed floodFill so that sometimes it recursed in the order up/down/left/right, and other times it recursed in the order up/left/right/down, it would sometimes fail to completely floodFill some regions.

d.   TRUE or FALSE:  A set can be a key in a dictionary, but a dictionary cannot be added to a set.

e.   TRUE or FALSE:  The syntax for Python expressions is recursive, in that a Python expression may contain another Python expression.

2.       [24 pts; 3 pts each] Very Short Answers:
Answer each of the following with only a few words or numbers.  Really, do not write long answers!

a.    What was the main reason that we used a closure in our animation run function?

b.   What is memoization?

c.    Why is recursion especially well-suited for creating fractals?

d.   List two problems that are most easily solved using backtracking.

e.   What is the purpose of the __init__ method?

f.     Write one line of Python that tells Tkinter to call the function named “foo” whenever the user presses the mouse, where foo is defined to take one parameter (the event object).

g.    If (as in the notes) we consider a Level 0 Koch Snowflake to be just a straight line (not a triangle, so this is really one-third of a snowflake), then sketch a Level 2 Koch Snowflake and clearly identify all the Level 1 Koch Snowflakes within it.

h.   Say we start with a 5x5 board and fill the black squares as shown below (in the code from our notes, the black squares would be green, and the white squares would be cyan).  Then we right-click where the star is to start a floodFill from there.  Write the numeric labels that result in each cell after the floodFill completes.

Hint #1: the numbers are the depth at each cell, so some labels may occur more than once.
Hint #2:  Here is an excerpt of the floodFill code:
def floodFill(row, col, color, depth=0):
        …
        floodFill(row-1, col, color, depth+1)
        floodFill(row+1, col, color, depth+1)
        floodFill(row, col-1, color, depth+1)
        floodFill(row, col+1, color, depth+1)
 

3.       [15 pts; 3 pts each] Code Tracing.  Indicate what each will print:

Statement(s):

Prints:

def f1(L, d):
    s = set()
    for x in L:
        try: s.add(d[x])
        except: s.add(x * 100)
    return sorted(s)
print f1(range(1,12,3),
         {1:3, 3:42, 4:5, 77:7, 10:3})

  

def f2(L):
    f = lambda x: 10*x+1
    L = [f(x) for x in sorted(L) if x != max(L)]
    return L
print f2([2, 5, 3, 4])







 

 

def f3(k):
    return lambda s1, s2: cmp(s1[k], s2[k])
L = ["this", "is", "so", "amazing"]
print sorted(L, f3(1))





 

z = 42
def f4(x, y=z):
    z = x+y
    return (x,y,z)
print [f4(1), f4(2, 3), f4(4)]






 

def f5(x):
    if ((x % 3) == 0):
        return [42]
    else:
        return [x, f5(x/2)]
print f5(26)







 

4.       [12 pts; 4 pts each] Reasoning about code
For each of the functions g, find values of the parameters so that g will return True.  Circle your answers.

def g(d):
    assert(type(d) == dict)
    s = set([d[key] for key in d])
    return (len(d) == len(s)**2 == 4)

def g2(f, x):
    assert(type(f) == type(g2))
    L = [ ]
    while (x != 0):
        L.append(x)
        x = f(x)
    return (L == range(100,0,-2))

 

 

def g3(L):
    def f(L, d):
        if (len(L) == 0):
            return [ ]
        else:
            assert(d < min(L))
            return [L[0]%d] + f(L[1:], d)
    return (f(L[1:], L[0]) == [2, 5, 3])
 

 

5.        [14 pts]  Short Free Response: countGifs
Write the recursive function countGifs that takes a path to a folder and returns the total number of GIF files (ending in “.gif”) in that folder or any subfolder (recursively).  If you do not remember the exact specs for the os functions you need (such as os.path.isdir), just use something close and you’ll get most of the points.
 

6.       [15 pts]  Free Response: “A” class
Write the class named “A” so the following test code works.
    assert(str(A(5)) == "A#1<x is 5, y is 42>")
    assert(str(A(5)) == "A#2<x is 5, y is 42>") # counter increases!
    assert(str(A(5, 99)) == "A#3<x is 5, y is 99>")
    b = A(2, 3).getSwappedA() # returns a new A with x and y swapped
    assert(type(b) == A)
    assert(str(b) == "A#5<x is 3, y is 2>")
 

7.  [15 pts]  Free Response:  halfSnake
Starting from the snake8.py file at the end of the Snake Tutorial, add the following feature:  when the user presses ‘h’, the snake is cut in half.  The front half of the snake, from the head to its middle, is unchanged.  But the back half of the snake disappears.  You may assume the snake is of even length.   Only include the new code required to do this, and when applicable, indicate the function to which the new code should be added.  (Note that any names reasonably close to the actual function names will be accepted.)
 

Bonus/Optional:  [2.5 pts]  In just a few words of plain English, in general, what does bonus1(n) compute
def bonus1(x, L=[42]):
    def g():
        (result, L[0]) = (L[0], L[0]+L[0])
        return result
    def f(f): L[0]=1; return sum([g() for f in range(f)])
    return f(x)
 

Bonus/Optional:  [2.5 pts]  Reasoning about code.  Find a value for s so that bonus2(s) returns True.
def bonus2(s):
    assert((type(s) == type("def")) and ("def" not in s))
    def g(s): return s*s
    return ([eval(eval(s))(g,x) for x in range(3,5)] == [12, 20])

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem