CMU 15-112: Fundamentals of Programming and Computer Science
Midterm 2

More important notes:

• Write your answers by hand with no calculators, no computers.
• No recursion.
• You may call almostEqual(x, y) and roundHalfUp(d) without writing them. Write everything else!

---

1. Free Response: Lists [20 points]

Write the function f(L, M) that takes two lists of integers, L and M, and returns a list containing the odd integers in M followed by the odd integers in L. The integers in the returned list must remain in the same order that they occurred in M or L.
Note: The function must also destructively remove the odd integers in L, though M should remain unmodified.

For example:

  L = [2, 3, 5, 6]
  M = [7, 8, 9]
  N = f(L, M)
  assert(L == [2, 6])       # odds destructively removed from L
  assert(M == [7, 8, 9])    # M is unmodified
  assert(N == [7, 9, 3, 5]) # odds in M then odds removed from L

---

2. Free Response: Animations [25 points]

Write appStarted, mousePressed, keyPressed, timerFired, and redrawAll (and any helper functions you use) to make an animation such that:

• The canvas starts with a single pink dot of radius 10 at the center of the canvas, with a counter drawn centered inside the dot initially set to 0.
• Each time the user clicks on the canvas, every dot that contains the location of that click has its counter increase by 1. However, if the click is not in any dot, then another pink dot is created at the click location with its counter set to 0.
• Each time the user hits the 'r' key, the app resets to its original condition with just one dot with its counter set to 0.
• When the user presses the 'g' key, a new green square with sides of length 10 appears in the bottom-right corner of the canvas.
  • This square's sides grow by 10 with each timerFired event. (Note that the bottom-right corner of the square stays located at the bottom-right corner of the canvas.)
  • Each time the green square hits the center of any pink dot, that pink dot disappears.
  • Note that all key and mouse presses are ignored while the green square is growing.
  • This continues until all the pink dots are gone, at which point the app resets as if 'r' was pressed.

You may abbreviate app, event, and canvas with a, e, and c.

---

3. Free Response: Lists, Dictionaries and Sets [30 points]

Write the function g(L) that takes a rectangular 2d list of integers L and returns a dictionary d mapping each integer value v in L to a set of all the integers in L that are adjacent to any occurrence of v in L. Do not destructively modify L. Note that each cell has up to 8 adjacent cells (including diagonals, just as in wordSearch).

For example:

  L = [ [ 3, 2, 5],
        [ 4, 3, 4],
        [ 1, 3, 3] ]

  assert(g(L) == {
        1 : { 3, 4 },
        2 : { 3, 4, 5 },
        3 : { 1, 2, 3, 4, 5 },
        4 : { 1, 2, 3, 5 },
        5 : { 2, 3, 4 }
      })

---

4. Short Answers [9 points total]

Clearly write your answers next to the problem number for each question, and circle them!


SA1. This is from our Snake case study. Mark each of the following with M, V, or C to indicate if it is in the Model, the View, or a Controller:

i) appStarted()
ii) takeStep()
iii) drawFood()
iv) placeFood()
v) app.foodPosition

SA2. Write the letters for ALL of the following that are stated in the Term Project Preview:

A) Focus both on user experience and on algorithmic sophistication, as both factor heavily in your tp grade.
B) We highly recommend that you make a game, though this is not required.
C) The best projects always use external modules such as pygame.
D) Think big! It's easier to prune an overly-large project idea than to grow an overly-small project idea.
E) If you do make a game, we encourage you to make several mini-games instead of one larger game.

SA3. Write the letters for ALL of the following that are TRUE:

A) Sets and dictionaries are both implemented using hashtables.
B) A dictionary's keys can be mutable, but its values must be immutable.
C) If L is a list and S is the set created by set(L), then L and S have the same length only if L has no immutable values in it.
D) Sets can be elements of other sets.
E) We cannot use indexing with sets.

---

5. Code Tracing [16 points total(4 each)]

What does the following code print?
Be certain to show your work for credit, and also very clearly circle your answer!

CT1 (of 4):

def ct1(d):
  s = set()
  for k in d:
    if k in d[k]:
      s.add(max(d[k]) % k)
  return s

print(ct1(
      { 2: { 3, 6 },
        4: { 2, 4, 5 },
        5: { },
        7: { 1, 7, 11 },
        8: { 1, 8, 84 },
      }))

CT2 (of 4):

import copy
def ct2(L, i):
  M = L
  N = copy.copy(L)
  L.append(i)
  M = M + [i+1]
  N[0] = i
  return (L, M, N)
print(ct2([1], 3))

CT3 (of 4):

import copy
def ct3(L):
  M = copy.copy(L)
  N = copy.deepcopy(L)
  M[0].append(3)
  N[0].append(4)
  L.insert(0, L.pop())

L = [ [ 1 ],
      [ 2 ] ]
ct3(L)
print(L)

CT4 (of 4):

# This is a helper function for ct4:
def f(L):
  i = 0
  while (i < len(L)*len(L[0])):
    r = i // len(L[0])
    c = i %  len(L[0])
    L[r][c] += i
    i += 2
  return i

def ct4(n):
  L = [ [ 1, 2, n   ],
        [ 3, 4, n+1 ] ]
  i = f(L)
  return (i, L)

print(ct4(3))

---

6. Bonus Code Tracing [Up to 4 points; 2 points each]

What does the following code print?
Be certain to show your work for credit, and also very clearly circle your answer!

Bonus CT1 of 2

# helper function for bonusCt1:
def z(n):
  L = [1]*2
  while len(L) < n:
    L, M = [1]*2, L
    for i in range(0, len(M)-1):
      L.insert(-1, M[i]+M[i+1])
  return L

def bonusCt1(n):
  return (int(''.join([str(v) for v in z(n)])),
          sum(z(n*2)))
print(bonusCt1(5))

Bonus CT2 of 2

def bonusCt2(n):
  M = [ list(range(1, n+1)) ]
  for k in range(1, n):
    z = 1+max(M[-1])
    M.append(list(range(z, z+n)))
  i = 1
  while True:
    try:
      j,k = i//n,i%n
      if (M[j][k] < 0): i += 1; continue
      m = i+i+1
      while True:
        try:
          q,r = m//n,m%n
          M[q][r] = -abs(M[q][r])
          m += i + 1
        except:
          break
      i += 1
    except:
      break
  return max([max(row) for row in M])
print(bonusCt2(10))

---