15-112 Midterm #2 – Fall 2013
80 minutes
Score = RawScore + 5.5 
 

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

a.    TRUE or FALSE:  Our Connect4 code used an unmodified version of WordSearch to check for wins.

b.   TRUE or FALSE:  The main advantage of using a “with” statement to read a file is that it will automatically create a new file if one does not already exist.

c.    TRUE or FALSE:  The main advantage of using isinstance(x,A) rather than (type(x) == A) is that isinstance works for any class, but type only works for built-in classes.

d.   TRUE or FALSE:  The syntax *L is used both to pack values into a list (when used in a “def”) and also to unpack values from a list (when used outside a “def”).

e.   TRUE or FALSE:  Both recursive insertionsort and recursive quicksort repeatedly split the list into a left part that is less than some value and a right part that is greater than that same value.
 

2.        [30 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 did we do to speed up our recursive Fibonacci function and why did it make the function run so much faster?
 

b.   Why is it hard to write a recursive lambda function?
 

c.    How did we use classes to eliminate the need for globals and closures in our animations?
 

d.   Say you have a function that takes a (possibly-large) list of words and returns a random wordsearch with all the words in it.  Your function is slow, so you use memoization to speed it up.  Why was that a bad idea?
 

e.   Describe a (possibly sub-optimal) way to implement hash(s) for some string s.
 

f.     Describe a specific key advantage of using BoardGame rather than just Animation as the superclass when writing a TicTacToe class.
 

g.    What, precisely, could go wrong if mutable values were allowed in sets?
 

h.   root.bind takes two parameters.   What is the type and the purpose of each of these?
 

i.      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.
 

j.     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, val=42):
    seen = set()
    def f(val):
        for d in L:
            for k in sorted(d.keys()):
                if (val in d[k]): return k
    while (val not in seen):
        seen.add(val)
        print val,   # don’t miss this!
        val = f(val)

print f1([{2:range(3,5),
           4:set([42,99])},
          {3:map(max,[[-1,1,0],[0,2,-42]])},
         ])











 


def f2(L):
   def cmpMaker(k):
       return lambda s1, s2: cmp(s1[k], s2[k])
   return sorted(L, cmpMaker(2))

for v in f2(["four", "score", "and", "seven"]):
   print v







 


def f3(L):
    s = set()
    for val in L:
        try: s.add(val)
        except: print "*",val,
    return sorted(s)
print f3([5, {4:3}, [2], (1,0)])





 


def f4(x):
    print x,  # don't miss this!
    if (x < 2):
        return 42
    else:
        return x + f4(x/2)
print f4(5)






 


def f5(L):
    if (len(L) == 0):
        return []
    else:
        a = [L[0]] if (L[0]%2 == 1) else [ ]
        return f5(L[1:]) + a
print f5(range(-4,4))







 

 

4.       [10 pts]  Short Free Response: findLargestFolder
Write the function findLargestFolder that takes a path to a folder and returns the path to the largest folder within that folder or any of its subfolders.  We will say that the size of a folder equals the sum of the sizes of all the non-folder files it directly contains.  Note that the size of a folder does not depend on the size of any folders it contains.  That is, if folder A contains folder B, and folder B contains file F, then F adds to the size of B, but not to the size of A.  Also note that findLargestFolder(F) might return F itself.  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.
 

5.       [10 pts] Free Response:   myReduce
Write the function myReduce so the following test code works.  Note that myReduce works similarly to reduce, and you may not call reduce in your solution.
     assert(myReduce(operator.add, range(3,6))    == (3+4+5))
    assert(myReduce(operator.mul, range(3,6), 2) == (2*3*4*5))


 

6.  [10 pts] Free Response:  Q and PQ
Write the Q and PQ classes so the following test code works.  Note that your PQ class may only have one method -- remove – and it does not have to be very efficient.  Also, note that the class Q implements a "Queue", so Q.remove will return the least-recently-added value (so this is first-in first-out).  Also, the class PQ implements a "Priority Queue", so PQ.remove will return the smallest value regardless of when it was added.

 q = Q()
 assert(str(q) == "<Q of size 0>")
 q.add(5)
 q.add(3)
 assert(str(q) == "<Q of size 2>")
 assert(q.remove() == 5) # first-in, first-out!
 assert(str(q) == "<Q of size 1>")
 assert(q.remove() == 3)
 assert(str(q) == "<Q of size 0>")

 q1 = Q()
 q1.add(42)
 q2 = Q()
 q2.add(42)
 q3 = Q()
 q3.add(99)
 assert(q1 == q2)
 assert(q1 != q3)

 pq = PQ()
 assert(type(pq) == PQ)
 assert(isinstance(pq, Q))

 pq.add(4)
 pq.add(1)
 pq.add(2)
 pq.add(3)
 assert(str(pq) == "<PQ of size 4>")
 assert(pq.remove() == 1)
 assert(pq.remove() == 2)
 assert(str(pq) == "<PQ of size 2>")
 

7.  [20 pts]  Free Response:   Kings Tour Editor
Without using BoardGame or Animation or any classes/OOP (and no globals), write a simple “kings tour editor”.  As you should recall from hw6, a kings tour is an 8x8 board full of integers from 1 to 64, where each integer is a legal king move away from the next-larger integer.  Kings in a given cell can move to any of the 8 adjacent cells, including diagonals.  Here, you will create a simple kings tour editor.  The board is initially an empty grid.  Each time the user clicks in a cell, the next number in the sequence appears in that cell.  If the moves entered are all legal to that point, the cells should have a green background.  Otherwise, they should have a red background.  Pressing ‘u’ should undo the last move, and this can be repeated until the board is empty.  You may assume that the run function is written for you.
 

8A)  Bonus/Optional:  [2.5 pts]  What will this print?

def b(*args):
    if (args == ()): return lambda x: 10*x-5
    f,g,x = args
    def b(f,g, x1,x2,e):
        x = (x1+x2)/2.0
        if (f(x) == g(x)): return x
        elif abs(f(x)-g(x))<e: return x
        elif f(x)>g(x): return b(f,g,x,x2,e)
        else: return b(f,g,x1,x,e)
    (d,e) = (2, 0.1)
    return b(f,g,x-d,x+d,e)
def q(q): return q**2+16
print b(q, b(), 2)


8B)  Bonus/Optional:  [2.5 pts]  Free Response:  (a + b)n.
Without using iteration (so only using recursion), write the function f(n) that returns the coefficients of the expansion of (a+b)n.  For example, (a+b)3 = 1a3 + 3a2b + 3ab2 + 1b3, so f(3) returns the list [1,3,3,1].