15-112 Fall 2011 Midterm 2 (80 minutes)

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

a. TRUE or FALSE: We create a Struct() to hold the values in canvas.data, but we could have used a dictionary instead, requiring just a slight change in the syntax to get or set values in canvas.data.

b. TRUE or FALSE: Recursion may be more elegant at times, but it is not more powerful, as anything that can be programmed using recursion can also be programmed without it.

c. TRUE or FALSE: Because root.mainloop is non-blocking, any code in the run function after the call to root.mainloop must not call root.mainloop again, or we’ll have two mainloops running at once.

d. TRUE or FALSE: In general, memoization trades off increased space for decreased time.

e. TRUE or FALSE: In floodFill, after filling a pixel, we must recurse up, down, left, and right from that pixel, but we can do so in any order (say, left, down, right, up).

f. TRUE or FALSE: Tkinter generally draws using absolute coordinates whereas Turtle graphics generally draws relative to the turtle’s current location and direction.

g. TRUE or FALSE: In practice, recursive functions without base cases do not run forever, but instead lead fairly quickly to a stack overflow exception.

h. TRUE or FALSE: The following two lines will result in a visible blue frame around a green rectangle:
canvas.create_rectangle( 50, 100, 150, 200, fill="blue", outline="blue", width=4)
canvas.create_rectangle( 50, 100, 150, 200, fill="green", width=0)

i. TRUE or FALSE: If we have two unordered lists each with N integers, it takes at least O(N**2) time (in the worst case) to verify whether or not the lists have any elements in common.

j. TRUE or FALSE: In our Snake implementation, on an NxN board, moving the snake ahead by one square requires O(1) time at first, but increases to O(N**2) time as the snake grows.

2. [15 pts; 3 pts each] Very Short Answers:
Answer each of the following with only a few words or numbers. Longer answers will be incorrect.

a. In just a few words, explain why we used a “for” loop in our recursive solution to permutations(a).

b. In our Tetris design, rather than first test if a rotation is valid, we instead just do the rotation, then undo it if it was not valid. In just a few words, why did we choose this approach?

c. If a drawing of a 5-pointed star in Python comes out upside down, what is the most likely bug?

d. If we adapted our Snake game to use Turtle graphics rather than Tkinter, we would have to change some parts of the code but not others. Circle each part that would require changes:

Model View Controller

e. If (as in the notes) we consider a Level 0 Sierpinski Triangle to be just a solid black triangle, then sketch a Level 2 Sierpinski Triangle and clearly identify all the Level 1 Sierpinski Triangles within it.

3. [15 pts; 5 pts each] Indicate what each will print or draw (assume a 400x400 canvas):

Statement(s):	Prints/Draws:
canvas.create_rectangle(50, 50, 350, 350) canvas.create_line(50, 50, 350, 350) canvas.create_oval(100, 200, 300, 400, fill="gray") k = 0 location = N for c in "ABCDEF": location = S if location == N else N canvas.create_text(350-k, 50, text=c, anchor=location) k += 60
def f(canvas, x, y, r): if (r > 10): pts = [(x-r,y),(x,y+r),(x+r,y)] canvas.create_polygon(pts, fill="black") canvas.create_rectangle(x-r/10,y-r, x+r/10,y, fill="black") f(canvas, 400-x/2, y/2, r/4) f(canvas, 200, 200, 200)
def f(x, y): print "f", x, y # don't miss this! if (x == 0): return "" else: return str(x)[0] + f(x>>y,y+1) print f(20,1)

4. [10 pts; 5 pts each] Reasoning about code
In these exercises, you should provide the arguments that cause the function to return the specified value. In most cases, there are many valid answers. You only need to provide one of them.

def f(n):
    if (n == 0):
        return (0,0)
    else:
        (x,y) = f(n/10)
      return (x+1,y+(n%10))

# provide a value of n where f(n) returns (5,43)

def f(canvas, a):
    canvas.create_rectangle(50, 50, 350, 350)
    for i in xrange(len(a)):
        for j in xrange(a[i]%10):
            x = 50+j*75
            y = 350-i*75
            fill = "gray" if (a[i]>10) else "black
            canvas.create_oval(x-10,y-10,x+10,y+10,fill=fill)

# provide a value of a where f(canvas, a) results in this drawing:

5. [10 pts] Free Response: recursion 1
Write the recursive function fact(n) that takes a non-negative integer n and returns n!, or n factorial, which is the product of n*(n-1)*…*1. By definition, 0! equals 1. Do not worry about non-integer or negative values.

6. [20 pts] Free Response: recursion 2
Write the function listEmptyFolders(path) that returns an alphabetized list of the names (not the paths) of all the empty folders starting from the given path, where an empty folder does not contain any files or other folders. If the path is not a folder (or not even a string), listEmptyFolders(path) should not crash, but should just return the empty list.

7. [20 pts] Free Response: animation
Assuming run() is already written and the canvas is 500x500, write init, timerFired (except the part that calls timerFired again), keyPressed, and redrawAll to make a simple analog stopwatch with a second hand (but no minute hand or hour hand). Your redrawAll should create only two objects – a circle and a line. At the start, and whenever the user presses ‘r’ (for ‘reset’), the second hand points directly up and does not move. Then, when the user presses ‘g’ (for ‘go’), the hand starts moving clockwise (of course) at the rate of one revolution per minute. When the user presses ‘s’ (for ‘stop’), the hand stops but does not reset to 0. Subsequent presses of ‘g’ and ‘s’ will make the hand go and stop again, all without resetting. Your solution must move smoothly, even though calls to timerFired may vary in frequency, so you must use time.time(), which returns the number of seconds since some arbitrary time many years ago.

Bonus/Optional

a. Bonus/Optional: [2.5 pts] What will this print?

def f(g): return lambda x: g(*range(x,x+3))
@f
def g(*f): return (f[0]+f[1],f)
print g(4)

b. Bonus/Optional: [2.5 pts] What will this print?

def f(m,n,d=0):
    print " "*d,m,n
    return (not m and (n+1)) or ((not n) and f(m-1,1,d+1))\
           if (n*m == 0) else f(m-1,f(m,n-1,d+1),d+1)
print f(1,3)