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

See the midterm2 frontmatter. 80 minutes total..

PART 1

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

import copy
def ct1(n):
    M = [list(range(n)), list(range(n,0,-1))]
    P = M
    Q = copy.copy(M)
    R = copy.deepcopy(M)
    M[0][0] = n+1
    P[1] = n+2
    Q[0].reverse()
    R.pop()
    return [P, Q, R]
print(ct1(2)) # careful with brackets and commas!

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

def ct2(d):
    s, t, u = set(), set(), set()
    for k in d:
        s.add(k)
        for v in d[k]:
            if v%2 == 0:
                t.add(v)
            else:
                u.add(v)
    return { min(s):t, max(s):u }
print(ct2({ 3:[1,2,4,1], 1:[5,5], 2:[0,5] }))

CT3 (5 points):
Indicate what this code prints.

def ct3(n):
    if (n == 0):
        return (0, 1)
    else:
        x, y = ct3(n//10)
        if (n%2 == 0):
            return (x + (n%10), y)
        else:
            return (x, y * (n%10))
print(ct3(324508))

RC1 (5 points):
Find a value for M such that rc1(M) returns True.

def rc1(M):
    r,c = len(M), len(M[0])
    assert(r == 2)
    assert(c > 0)
    for i in range(r*c):
        assert(M[i%r][i//r] == i)
    return (sum(M[-1]) == 9)

TRUE/FALSE (10 points total, 1pt ea):

The next few TRUE/FALSE questions concern fractals:

1) A fractal is an image that is made up of smaller versions of itself.

2) In a Sierpinski Triangle, the only time we actually draw is at level 0. 
    Additionally, level N only ever calls level N-1 in the recursive case.

3) In our Freddy Fractal, the only time we actually draw is at level 0. 
    Additionally, level N only ever calls level N-1 in the recursive case.

Mark each statement as either TRUE or FALSE. Each question concerns the Word 
    Search case study (Which consists of the wordSearch function plus its two 
    helper functions)
Note: the outermost or top-level function is "wordSearch" itself.  
That function calls the middle function, and that function in turn calls 
the innermost function.

4) We represented the board as a 1d list of strings.

5) Of our 3 functions, only the innermost function actually compared letters in 
    the word to letters on the board.

6) Of our 3 functions, the middle function's main role is to choose a specific 
    direction, given a specific starting location.

The next few TRUE/FALSE questions concern efficiency:

7) To find a single value in an unsorted list, it is faster to use linearSearch 
    than to first sort the list and then use binarySearch.

8) In the proof that mergesort is O(NlogN), the N comes from the fact that there 
    are approximately N passes, and the logN comes from the fact that on each 
    pass we do half as much work as the previous pass.

The next few TRUE/FALSE questions concern recursion:

9) Calling a recursive function without a proper base case typically results in 
    stack overflow.

10) Folders can contain folders, so they are a recursive data structure, which 
     is why it is so helpful to use recursion to find files inside nested 
     folders.

PART 2

Free Response 1: makeEdits(M, E) [15 points]

Note: this is similar to a question on quiz8, but different in important ways. Read this carefully!

Background: say we have this 2d list M:

M = [ [ 1, 2, 3 ],
      [ 4, 5, 6 ],
      [ 7, 8, 9 ] ]

Also, we have this list of strings describing non-destructive edits to make on M:

E = [ 'add row 0 to row 1',
      'add 10 to col 0',
      'add row 2 to row 0',
    ]

Note that edits will always either add a row to another row, or add a constant to a column.

To make the first edit, we add row 0 to row 1 on the original list, to get:

    [ [ 1, 2, 3 ],
      [ 5, 7, 9 ],
      [ 7, 8, 9 ] ]

To make the second edit, we add 10 to each value in col 0 in that list, to get:

    [ [ 11, 2, 3 ],
      [ 15, 7, 9 ],
      [ 17, 8, 9 ] ]

Finally, to make the last edit, we add row 2 to row 0 on the that list, to get:

    [ [ 28, 10, 12 ],
      [ 15,  7,  9 ],
      [ 17,  8,  9 ] ]

With this in mind, write the function makeEdits(M, E) that takes a rectangular (but not necessarily square) 2d list M and a 1d list of edits E, and nondestructively returns the 2d list that results from making the edits in E on M.

You can assume that all the edits are of the form described above, and always contain legal values.

We will grade using additional test cases, so do not hardcode! You may want to add your own test cases, or at least try some lists with different shapes/sizes/edits.

Note: M can be larger than 10x10.
Hint: You may want to use s.split() in your answer.
Hint: you may want to use copy.deepcopy(M) in your answer.

import copy, math

def makeEdits(M, E):
    return 42

def testMakeEdits():
    print('Testing makeEdits()...', end='')
    M = [ [ 1, 2, 3 ],
          [ 4, 5, 6 ],
          [ 7, 8, 9 ] ]
    E = [ 'add row 0 to row 1',
          'add 10 to col 0',
          'add row 2 to row 0',
        ]
    N = [ [ 28, 10, 12 ],
          [ 15,  7,  9 ],
          [ 17,  8,  9 ] ]
    assert(makeEdits(M, E) == N)
    print('Passed!')

testMakeEdits()

Free Response 2: Scoreboard Class [20 points]

Write the Scoreboard class so that the following test code passes. Be sure not to hardcode, so that any similar test code also passes.

class Scoreboard(object):
    def __init__(self, scores):
        #Finish writing this class
        pass

def testScoreboardClass():
    print('Testing Scoreboard class...', end='')
    # Create a Scoreboard with these initial scores
    sb1 = Scoreboard({'Alice':3, 'Bob':4})
    assert(sb1.getScore('Alice') == 3)
    assert(sb1.getScore('Bob') == 4)
    assert(sb1.getScore('Cal') == None)
    assert(sb1.leaders() == { 'Bob' }) # A set of all the leaders

    sb1.addScore('Alice', 2) # Alice just scored 2 points!
    assert(sb1.getScore('Alice') == 5) # Now she has 5 points
    assert(sb1.leaders() == { 'Alice' }) # Alice has 5, Bob has 4

    sb1.addScore('Cal', 2)   # Cal wasn't there, now Cal is, with 2 points
    assert(sb1.getScore('Cal') == 2)
    sb1.addScore('Cal', 3)
    assert(sb1.getScore('Cal') == 5)
    assert(sb1.leaders() == { 'Alice', 'Cal' }) # Alice and Cal both have 5

    assert(sb1.getAll() == { 'Alice':5, 'Bob':4, 'Cal':5 })

    sb2 = sb1.getCopy() # This is a copy of sb1, where changes to the copy
                        # do not affect the original, and vice versa
    assert(sb2.getAll() == { 'Alice':5, 'Bob':4, 'Cal':5 })
    sb2.addScore('Bob', 3) # Bob now has 7 in sb2, but still has only 4 in sb1
    assert(sb2.leaders() == { 'Bob' })
    assert(sb1.leaders() == { 'Alice', 'Cal' })
    print('Passed!')

testScoreboardClass()

Free Response 3: evensAreSorted(L) [15 points]

Notes:

You must use recursion for this problem, and you may not use loops (no 'for' loops or 'while' loops)
As always, you may use helper functions and wrapper functions.
This is not a backtracking problem.

Without using loops or strings, write function evensAreSorted(L) that takes a possibly-empty list L and returns True if the evens are sorted in strictly increasing order. Odds are ignored. Lists containing no evens (including the empty list) should return True. Look at the test cases for some specific examples.

More important notes:

You may not use strings.
You may use list slicing, but you may not use builtin functions that are O(N) or worse -- so you may not use min, max, sum, reverse, sort, etc.
You may not create a new list containing only the even digits

def evensAreSorted(L):
    return 42

def testEvensAreSorted():
    print('Testing evensAreSorted()...', end='')
    assert(evensAreSorted([2, 4, 8]) == True)
    assert(evensAreSorted([1, 2, 3, 4, 5, 8]) == True)
    assert(evensAreSorted([4, 2, 4, 2, 4]) == False)
    assert(evensAreSorted([1,2,3,3,2,1]) == False)
    assert(evensAreSorted([42, 33, 10, 80]) == False)
    assert(evensAreSorted([4]) == True)
    assert(evensAreSorted([9]) == True)
    assert(evensAreSorted([]) == True)

    print('Passed!')

testEvensAreSorted()

Free Response 4: makeWordLadder(L) [20 points]

Notes:

This is a backtracking problem. You MUST use backtracking properly to receive points on this problem, even if there is some other way to solve the problem.
You MAY use 'for' or 'while' loops here, but you also must use recursion properly.

Background: Two strings in a 1D list are considered "connected" (a coined term) if they are adjacent and the last (i.e. rightmost) character of the first string is the same as the first (i.e. leftmost) character of the next string. For example, in the list ['abc', 'cat', 'cog']:

'abc' and 'cat' are connected because the nearest characters are both 'c'
'cat' and 'cog' are NOT connected because the nearest characters are 't' and 'c'
'abc' and 'cog' are NOT connected, because 'cat' is in the way

Also: given a list of strings L, we will say that it the list is a word ladder if every consecutive pair of strings is connected.
Here is a simple word ladder:

  
    ['abc', 'cde', 'efg']

Or for example, consider this list, which is NOT a word ladder:

    ['abc', 'cde', 'doa', 'ead']

All of the following reorderings of L ARE word ladders:

    ['abc', 'cde', 'ead', 'doa']
    ['doa', 'abc', 'cde', 'ead']
    ['ead', 'doa', 'abc', 'cde']
    ['cde', 'ead', 'doa', 'abc']

With this in mind, using backtracking, write the function makeWordLadder(L) that takes a list of non-empty strings as L and returns a new list that has the same values of L but reordered (if necessary) so that the result is a word ladder (that is, each adjacent pair of strings is connected), or None if there is no such list.

If there is more than one valid answer, you can return any one of them. Also, if L is already a word ladder, you can simply return L if you wish.

For example, makeWordLadder(['aba', 'ca' ,'aa']) has to return either one of ['ca', 'aba', 'aa'] or ['ca', 'aa', 'aba'] (your choice).

def makeWordLadder(L):
    return 42

def testMakeWordLadder():
    print('Testing makeWordLadder()...', end='')
    assert(makeWordLadder(['aba', 'ca' ,'aa']) in [['ca', 'aba', 'aa'],
                                                  ['ca', 'aa', 'aba']])
    assert(makeWordLadder(['efg', 'abc', 'ghi', 'cde']) 
                                              == ['abc', 'cde', 'efg', 'ghi'])
    assert(makeWordLadder(['a', 'at', 'a', 'xa', 'a']) 
                                              == ['xa', 'a', 'a', 'a', 'at'])
    assert(makeWordLadder(['ab', 'cu', 'bu']) == None)
    assert(makeWordLadder(['abc']) == ['abc'])
    assert(makeWordLadder([]) == [])
    print('Passed!')

testMakeWordLadder()

PART 3

BonusCT1 [+2 points]

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

def f(L):
    i = len(L)//2
    return L if i==0 else f(L[:i]) + f(L[i+1:])
def g(L):
    if L == [ ]: return L
    return h(L[-1]) + g(L[:-1])
def h(n):
    a,b = n//10,n%10
    return [n] if ((a+b)%10 == 0) else [ ] 
def bonusCt1(L):
    return g(f(L))
print(bonusCt1(list(range(32))))

BonusCT2 [+2 points]

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

def bonusCt2(L,d=1):
    if (L == [ ]):
        return L
    else:
        try:
            return bonusCt2(L[0],d+1) + bonusCt2(L[1:],d)
        except:
            return [L[0]*d] + bonusCt2(L[1:],d)
print(bonusCt2([1,[2],[[3],4]]))

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

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