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


Midterm2 Version A


Do not start (and do not look at the problems) until you are instructed to do so!

For any tech fails (laptop or internet stops working, etc.):
Important notes:
  1. We suggest you do not use your browser's zoom feature. Instead...
    • Click near the left edge to make font smaller.
    • Click near the right edge to make font bigger.
  2. You will have 75 minutes once the proctor says to start.
  3. You will have brief additional time after we stop to scan and submit your solutions.

  4. Just before the exam...
    1. Have a fully-charged smartphone and laptop, and still plug both in if possible
    2. Log into Gradescope on your phone
    3. Change the screen timeout setting on your phone to never, so your screen doesn't go black if you don't interact with your screen for a while.
      • iPhones: Settings / Display & Brightness / Auto-Lock / Never
      • Android: Settings / Display / Screen timeout / 10 minutes (or the maximum amount of time)
    4. Turn on Do Not Disturb (or otherwise turn off all notifications).
    5. Position your webcam so we can see:
      • Your desk
      • The paper you are working on
      • Your writing utensil(s)
      • Both of your hands
      • Your phone

  5. During the exam:
    1. You may not ask questions during the exam.
      • If you are unsure how to interpret a problem, take your best guess.
    2. You may not touch your laptop or webcam.
      • This includes muting yourself at any point; the proctors may mute you though.
    3. All of these must be visible at all times:
      • Your desk
      • The paper you are working on
      • Your writing utensil(s)
      • Both of your hands
      • Your phone, with the exam webpage
    4. For any tech fails (laptop or internet stops working, etc.):
      1. Stop taking the exam
      2. Fill out this Google Form immediately
      3. IMMEDIATELY scan/photograph and email your incomplete exam (along with any scratch work) directly to mdtaylor@andrew.cmu.edu and koz@andrew.cmu.edu
      4. We will email you soon to ask about your tech fail, and to set up an alternate exam time if we believe the issue was out of your control. Note that this exam will be completely different, shorter, and slightly more difficult.

  6. After the exam:
    1. Follow all proctor instructions on how to end the exam.
    2. Keep everything in view (as noted above) until the proctor calls "time".
    3. When instructed, use your phone to scan your exam and submit the PDF to Gradescope.
    4. After submitting to Gradescope, hold your phone up to the webcam to show the receipt.
    5. Even then, remain in exam mode until the proctor calls "all clear"


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:
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, 7 },
        5: { },
        6: { 1, 6, 8 },
        8: { 1, 8, 82 },
      }))


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], 4))


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 = [ [ 2, 5, n   ],
        [ 4, 6, n+1 ] ]
  i = f(L)
  return (i, L)

print(ct4(2))




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))