15-112 Fall 2012 Quiz 10 part 1 (30 pts / 10 pts each)
7 Minutes.  No calculators, no notes, no books, no computers.
Solutions that use loops will receive no credit.

1.       Be here.  (Students received +10 points for writing their names on the quiz!)

2.       Write fact(n) that recursively computes n! (n factorial).

3.       Write fib(n) that recursively computes the nth Fibonacci number as we did in the course notes (starting at n==0).

15-112 Fall 2012 Quiz 10 part 2 (70 pts / 10 pts each)
25 Minutes.  No calculators, no notes, no books, no computers.
Solutions that use loops will receive no credit.

1.       Consider the following two versions of fib(n):
    def fib(n): return 1 if (n < 2) else fib(n-1)+fib(n-2)
and
    def fib(n): return (n<2)*1 + (n>=2)*(fib(n-1)+fib(n-2))
The first version works properly, but the second one does not.  Very briefly, what error occurs and why?
 

2.       Consider the following failed attempt to memoize fib:
    def fib(n): return 1 if (n < 2) else fib(n-1)+fib(n-2)
    memoizedValues = { }
    def memoizedFib(n):
        if (n not in memoizedValues):
            memoizedValues[n] = fib(n)
        return memoizedValues[n]
    print memoizedFib(40)
When this code runs, it works in that it prints the correct value, but it takes a really long time, so the memoization part really did not work.  Very briefly, why not?
 

3.       If a Level 0 tree fractal is a straight vertical line, and a Level 1 tree fractal is a “Y”, draw a Level 2 tree fractal.  (We will accept either of two possible answers here.)
 

4.       Here is the insertionsort code from the class notes (with the function renamed “f”):
    def f(L):
        if (len(L) < 2):
            return L
        else:
            first = L[0]
            rest = f(L[1:])
            lo = [x for x in rest if x < first]
            hi = [x for x in rest if x >= first]
            return  lo  +  [first]  +  hi
Make just a couple very simple edits to this code so that instead of insertionsort it implements quicksort.
 

5.       Say we start with a 4x6 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.

6.       Here is the powerset code from the class notes, with parts of two lines removed:
    def powerset(a):
        # returns a list of all subsets of the list a
        if (len(a) == 0):
            return [[]]
        else:
            allSubsets = [ ]

            for subset in ____________________________________:

                allSubsets += [subset]

                allSubsets += ______________________________________________

            return allSubsets
Fill in the blanks with the missing code.
 

7.       What will be printed when the following code is run (hint: it prints a total of 10 lines):
def f(x, depth=0):
    print "   "*depth + "f(%d)" % (x)
    if (x < 10):
        result = x**2
    else:
        result = f(x%10, depth+1) + f(x/10, depth+1)
    print "   "*depth + "--> %d" % (result)
    return result
f(123)
 

8.        [Bonus/Optional, 5 pts]  What will this print?
def f(A):
    if (len(A) < 2): return A
    return [A[A[-1]%len(A)]] + f(A[:-1])
print f([2,3,5,7,11])