CMU 15-112: Fundamentals of Programming and Computer Science
Midterm 3 (80 min.)

This midterm exam was offered online in three parts - SA and CT in part 1, FR in part 2, and bonus CTs in part 3. Students may begin in any section, but cannot move to another until the current section is submitted. The exam is 80 minutes in length.

Midterm3 Part 1

Short Answers (20 pts, 2 pts each)

Modify the dictionary so that the letters corresponding to the true statements map to True and the letters corresponding to the false statements map to False.
1. An O(N**2) algorithm can perhaps run faster than an O(NlogN) algorithm for some small N, but not for sufficiently large N.
2. Our proof that selectionsort is O(N**2) involves summing the integers from 1 to N/2.
3. Our proof that mergesort is O(NlogN) shows that there are about 3N steps on each pass -- N comparisons, N copies, and N swaps.
4. If a recursive function lacks a base case, calling it will most likely result in stack overflow.
5. In our implementation of a Sierpinski Triangle, the recursive part only draws one of three sides of the triangle.
```
      {
        "A": False,
        "B": False,
        "C": False,
        "D": False,
        "E": False,
      }
  
```
Modify the dictionary so that the letters corresponding to O(1) operations map to True and the letters corresponding to non-O(1) operations map to False.

You should assume that L is a list and S is a set.
1. max(L)
2. L.count(val)
3. len(L)
4. val in S
5. L.append(item)
6. set(L)
7. val in L
```
      {
        "A": False,
        "B": False,
        "C": False,
        "D": False,
        "E": False,
        "F": False,
        "G": False,
      }
  
```
Approximately how many passes does mergesort require when sorting a list with 1 million elements?
List one function family that is smaller than N**0.5 but larger than 1.
If selectionsort on some list L requires 1 billion steps, how many steps would selectionsort require on a list M, where M = L*10?
If f(1 million) takes 2 seconds, and f(7 million) takes 14 seconds, what is the most likely function family that f runs in?
The following is a snapshot of xSortLab running selectionsort. What are the indexes of the next two values to be swapped?
The following is a snapshot of xSortLab running mergesort. What is the index of the next value to be copied to the temporary list?

Fill in the blank so that the following computes fib(n), the nth fibonacci number:

    def fib(n):
        if __________________ : # <-- HERE
            return 1
        else:
            return fib(n-1) + fib(n-2)

The following picture shows both Level 1 and Level 2 of a fractal.

With this in mind, fill in the blank so that the following code draws that fractal at the given level:

  starter-code: |
    def drawFractal(app, canvas, level, x0, y0, size):
        if level == 0:
            canvas.create_rectangle(x0, y0, x0+size, y0+size, fill='black')
        else:
            drawFractal(app, canvas, level-1, x0, y0, size/3)
            ___________________ # <-- HERE

Code Tracing (15 pts, 7.5 pts each)

Indicate what each CT prints. Write your answer (and only your answer) in each box.

    class A(object):
        def __init__(self, x, y):
            self.x = x
            self.y = y
        def f(self):
            return self.x + self.y
        def g(self):
            return self.f()/10

    class B(A):
        def __init__(self, x):
            super().__init__(x, x**2)
        def g(self):
            return self.f()*10

    def ct1(x):
        a = A(x, 2*x)
        b = B(x)
        print( [ a.g(), b.g() ] )

    ct1(4)

    def f(n):
        # note: f(n) returns a string
        s = str(n)
        if (n < 2):
            return ('a' + s)
        elif (n % 5 == 0):
            return ('b' + s)
        else:
            return f(n//2) + ('c' + s) + f(n//4)

    print(f(11))

Midterm3 Part 2

Modifying Code [15 pts]

Note: this problem is a twist on a standard FR, since we will provide you with a sample solution which you then have to modify as described here.

Also note: here, you can use 'for' or 'while' loops if you wish, but you also must use backtracking properly to receive credit. Also, do not hardcode to any specific value of n.

Background: in chess, a king has up to 8 legal moves, one step in each of the 8 possible directions while remaining on the board. Also, a Kings Tour is similar to a Knights Tour. For a Kings Tour on an n-by-n board, you place the integers from 1 to n**2 on the board so that the move from each integer to the next (i.e. 1 to 2) is a legal King move. We will further require that 1 is always placed in the top-left corner.

Here, for example, is a 3x3 Kings Tour:
```
    [
     [ 1, 2, 3 ]
     [ 5, 4, 8 ]
     [ 6, 7, 9 ]
    ]
    
```
We will say that a Zagging Kings Tour (a coined term) is a Kings Tour where the king does not make the same move consecutively. In the example above, the king moves right to get from 1 to 2, and then right again to get from 2 to 3. This is two consecutive moves to the right, so the example is not a Zagging Kings Tour.

Here is a 3x3 Zagging Kings Tour:
```
    [
     [ 1, 2, 9 ]
     [ 3, 5, 8 ]
     [ 4, 7, 6 ]
    ]
    
```
For this problem, we will provide you with a working solution to Kings Tour. Your task is to convert that solution so that it instead returns a Zagging Kings Tour, or None if no such board exists for the given value of n.

The starter code includes make2dList and print2dList, so you can use those if you wish.

Also: there are no test cases here. Run the code and visually inspect the result yourself to verify that it is producing a Zagging Kings Tour.
```
Sample solution for Kings Tour is elided here.
```

FR1 [25 pts]

Note: you may use 'for' or 'while' loops here.

Write the File and Folder classes so that the test cases below pass. Do not use a dataclass. Do not hardcode your answers.

    def testFilesAndFolders():
        print('Testing File and Folder classes...', end='')

        foo = File('foo.txt', 25)
        assert(str(foo) == 'File(name=foo.txt,size=25)')

        folderA = Folder('A')
        assert(str(folderA) == 'Folder(name=A,fileCount=0)')

        folderA.add(foo)
        assert(str(folderA) == 'Folder(name=A,fileCount=1)')

        folderB = Folder('B')
        assert(str(folderB) == 'Folder(name=B,fileCount=0)')

        bar1 = File('bar1.txt', 100)
        assert(str(bar1) == 'File(name=bar1.txt,size=100)')
        bar2 = bar1.copyFile('bar2.txt')
        assert(str(bar2) == 'File(name=bar2.txt,size=100)')

        folderB.add(bar1)
        assert(str(folderB) == 'Folder(name=B,fileCount=1)')
        folderB.add(bar2)
        assert(str(folderB) == 'Folder(name=B,fileCount=2)')

        # The fileCount only counts files, not folder, and does
        # so only for files in this folder and not in any folders
        # within this folder.  Thus, when we add folderB to folderA,
        # it does not increase the fileCount of folderA
        folderA.add(folderB)
        assert(str(folderA) == 'Folder(name=A,fileCount=1)')

        # folder.getTotalFileSize() returns the sum of the sizes of
        # all the files in that folder plus all the sizes of files in
        # any folder recursively within that folder.
        # To do this, you must write getTotalFileSize() recursively

        # folderB contains 2 files each of size 100, so that's 200
        assert(folderB.getTotalFileSize() == 200)
        # folderA contains 1 file of size 25, but also contains
        # folderB which is of size 200, so that's 225 in total
        assert(folderA.getTotalFileSize() == 225)

        bar3 = bar2.copyFile('bar3.txt')
        folderB.add(bar3)
        # A new file was added to folderB, which is in folderA
        # Accordingly, the total file size of folderA has increased to 325
        assert(folderA.getTotalFileSize() == 325)

        print('Passed!')

    testFilesAndFolders()

FR2 [25 pts]

Note: for this problem alone, you must only use recursion. You must not use 'for' or 'while' loops to solve this problem.

Given a list L of integers, we will say that a value in L is an "island" (a coined term) if it is even and the values to the left and right of it are both odd, or if it is odd and the values to the left and right of it are both even. Note that the first and last values in the list cannot be islands.

With this in mind, write the recursive function islands(L) that takes a list L and returns a list containing only the islands in L, in the same order as they appear in L.

See the test cases below for some examples.

Note: once again, do not use 'for' or 'while' to solve this problem. The provided test code will not detect if you did that, but our TA's will check this, and if you use 'for' or 'while', you will receive 0 points for this problem.
```
  starter-code: |
    def testIslands():
        print('Testing islands()...', end='')
        assert(islands([ ]) == [ ])
        assert(islands([1, 2, 3]) == [ 2 ])
        assert(islands([1, 2, 4]) == [ ])
        assert(islands([1, 2]) == [ ])
        assert(islands([1, 2, 3, 5, 6, 7, 8, 10, 9]) == [ 2, 6, 7])
        print('Passed!')

    testIslands()
  
```

Bonus CT (up to 5 pts, 2.5 pts each)

    def bonusCt1(n=2):
        def f(n): return n if n < 2 else 2*n-1+f(n-1)
        def g(n): return n if n < 2 else 2*g(n-1)
        def h(n): return g(n)/f(n) == round(g(n)/f(n))
        return f(n) if h(n) else bonusCt1(n+1)
    print(bonusCt1())

    def bonusCt2(x):
        def f(g, x): return lambda y: g(x*y)
        def g(n): return 10+n
        return f(f(g, x),x+1)(x+2)
    print(bonusCt2(5))

CMU 15-112: Fundamentals of Programming and Computer Science Midterm 3 (80 min.)

Midterm3 Part 1

Midterm3 Part 2

Bonus CT (up to 5 pts, 2.5 pts each)

CMU 15-112: Fundamentals of Programming and Computer Science
Midterm 3 (80 min.)