CMU 15-112: Fundamentals of Programming and Computer Science
Quiz10a

See the quiz10 frontmatter. 20 minutes total..

PART 1

CT1 (15 points):
Indicate what this code prints.

def ct1(n):
    if (n <= 0):
        return [ ]
    elif (n%10 >= 5):
        return [n] + ct1(n//2)
    else:
        return ct1(n-2) + [-n]
print(ct1(15))

CT2 (15 points):
Indicate what this code prints.

def ct2(L, x):
    if L == [ ]:
        return L
    else:
        if L[0] > x:
            rest = ct2(L[1:], x+L[0])
            return [L[0]] + rest
        else:
            return ct2(L[1:], x)
print(ct2([2,3,4,5,6,1], 2))

RC1 (15 points):
Find a value for s such that rc1(s) returns True.

def f(s):
    # This is a helper function for rc1
    if (s == ''):
        return ''
    else:
        if (s[0].isdigit()):
            t = str(int(s[0]) - int(s[-1]))
        else:
            t = max(s[0], s[-1])
        return t + f(s[1:-1])

def rc1(s):
    return f(s) == '1b2'

PART 2

Free Response 1: getBottomUpColumn(M, col) [55] points]

Without using loops, write the recursive function getBottomUpColumn(M, col) that takes a rectangular 2d list M and a column index, and returns a 1d list containing the values in that column of M, from bottom to top. If there is no such column, return None. For example, given this 2d list:

    M = [[ 1, 2, 3],
         [ 4, 5, 6]
        ]

Then:

getBottomUpColumn(M, 0) returns [4, 1]
getBottomUpColumn(M, 1) returns [5, 2]
getBottomUpColumn(M, 2) returns [6, 3]

Also, getBottomUpColumn(M, 3) and getBottomUpColumn(M, -1) both return None.

You may not use loops, list comprehensions, strings, L.reverse(), or reversed(L)

Note that you may want to write getBottomUpColumn as a wrapper function for a recursive helper function (again, without using loops). Your choice.

def getBottomUpColumn(M, col):   
    return 42

def testGetBottomUpColumn():   
    print('Testing getBottomUpColumn()...', end='')
    assert(getBottomUpColumn([[1,2,3],[4,5,6]], 0) == [4, 1])
    assert(getBottomUpColumn([[1,2,3],[4,5,6]], 1) == [5, 2])  
    assert(getBottomUpColumn([[1,2,3],[4,5,6]], 2) == [6, 3])
    assert(getBottomUpColumn([[1,2,3],[4,5,6]], 3) == None)  
    assert(getBottomUpColumn([[1,2,3],[4,5,6]], -1) == None) 
    print('Passed!')
    print('Note: We may grade your code with additional test cases')


testGetBottomUpColumn()

PART 3

BonusCT1 [+2 points]

This is an optional bonus problem. Indicate what this code prints.

def bonusCt1(n):
    def f(x): return x and 2*x-1+f(x-1)
    def g(x): return x and 1+g(x//2)
    while f(g(n)) != n: n = f(g(n))
    return n
print(bonusCt1(100))

BonusCT2 [+2 points]

This is an optional bonus problem. Indicate what this code prints.

def bonusCt2(n):
    def f(n):
        if (n < 3): return n
        else: return f(n-1) - f(n-2) + f(n-3)//2
    return f(n)
print([bonusCt2(n) for n in range(17,19)])

CMU 15-112: Fundamentals of Programming and Computer Science Quiz10a

CMU 15-112: Fundamentals of Programming and Computer Science
Quiz10a