15-112 Fall 2011 Quiz 9-Redux
actualQuiz9Score = max(originalQuiz9Score, quiz9ReduxScore)
20 Minutes.  No calculators, no notes, no books, no computers.

1.  [15 pts]  Short Answers.   Consider this code:
def f(s,t):
    assert (type(s) == type(t) == str) and (len(s) == len(t))
    if (len(s) == 0):
        return ""
    else:
        i = len(s)/2
        c = s[i] if (s[i] == t[i]) else ""
        return f(s[:i],t[:i]) + c + f(s[i+1:],t[i+1:])
print f("abcdef","abodes")

a.       What will this code print?

b.      Give values of s and t such that f(s,t) returns "ok".

c.       In just a few words of plain English, describe what f(s,t) computes.

2.       [15 pts]  Short Answers.   Consider this code:
def f(x, y):
    assert ((type(x) == int) and (x >= 0) and
            (type(y) == int) and (y >= 0))
    if (y > x):
        return 0
    else:
        return 1 + f(x/y, y)
print f(35, 2)

a.       What will this code print?

b.      Give values of x and y such that f(x,y) returns 6.

c.       In just a few words of plain English, describe what f(x,y) computes.

3.       [20 pts]  Free Response:  numberOfEvens
Write the recursive function numberOfEvens(a) that takes a list a, that you may assume contains only integers, and returns the number of even numbers in that list.  You may not use loops or list comprehensions, just recursion.
 

4.        [50 pts]  Free Response:  folderWithMostFiles
Write the function folderWIthMostFiles(path) which returns the full path to the folder, starting from the given path, that contains the most files (not counting other folders).  You may assume the original path is to a folder, not a file.  Do not worry about ties.
 

5.  [5pts] bonus/optional: What will this code print?
def g(f,a):
    if (type(a) != list): return ["g",2*a]
    else: return [(lambda x: f(g,x))(x) for x in a]
def f(g, a):
    if (type(a) != list): return ["f",3*a]
    else: return [(lambda x: g(f,x))(x) for x in a]
print f(g, [1,[[2],3]])    # 3 pts
print f(g, g(f, [1,[2]]))  # 2 pts