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

More important notes:

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

---

1. Free Response: nthSandwich [25 points]

Note: to receive any credit on this problem, you must not use strings. This limitation is only for this problem.

We will say that an integer is a "sandwich" (a coined term) if it contains at least two digits and it starts and ends with the same non-zero digit d, and the digit d does not occur anywhere else within the number.

For example, these are all sandwiches:

  11
  202
  9359

And these all are NOT sandwiches:

  234 # start doesn't match end
  222 # start digit (2) occurs in middle
  220 # cannot end in 0

With this in mind, write the function nthSandwich(n) that takes a non-negative int n and returns the nth sandwhich, where nthSandwich(0) returns 11.

Again: do not use strings here.

---

2. Free Response: biggestRange [25 points]

For this problem, we are given a multi-line string that contains one or more lines of comma-separated data, where each line contains exactly one name (which can be anywhere on the line), along with one or more non-negative integers, like so:

  data = '''Fred,2,3,3
  8,Wilma,4
  9,1,5,6,Betty
  Barney,77'''

We will say that the "range" of the data on a given line is the difference between the largest and smallest integers on that line. Ranges are always non-negative, regardless of the order of the values on the line. If a line has only one value, then its range is 0.

Here are the ranges for the data above:

  Fred:   1 (3-2)
  Wilma:  4 (8-4)
  Betty:  8 (9-1)
  Barney: 0 (just one value)

With this in mind, write the function biggestRange(data) that takes a string as described and returns the name of the person with the biggest range.

In the data above, biggestRange(data) returns 'Betty'.

If there is a tie, you should return all the names who tied in a single comma-separated string in the same order as they appeared in the data. For example:

  data = '''10,Mike,2
  8,7,6,David
  Kyra,1,9'''

Here are the ranges for this data:

  Mike:  8 (10-2)
  David: 2 (8-6)
  Kyra:  8 (9-1)

Thus, for this data, biggestRange(data) returns 'Mike,Kyra'.

Hint: you may wish to use both s.split() and s.splitlines().

---

3. Free Response: Dot Around Dot [30 points]

Here you will write appStarted, mousePressed, timerFired, and redrawAll for an animation that works like so:

• The app starts with red circle of radius 100 drawn in the center of the window (do not hardcode the window's size).
• There also is a blue dot of radius 20 that is drawn so its center lies on the red circle's perimeter, with the blue dot initially at the top of the red circle (ie, at 12 o'clock).
• The blue circle moves clockwise, smoothly, around the red circle, at the rate of one revolution every 5 seconds. Note: do not change app.timerDelay -- keep it at 100, so there are 10 calls to timerFired per second.
• The blue dot has a counter drawn centered inside it. This is 0 at first, and each time the mouse is pressed inside the blue dot, this counter is increased by 1.
• If the mouse is pressed outside the blue dot, the counter decreases by 1, except if the counter would go negative, instead "Game Over" is displayed in the center of the window and all further events are ignored.

You should abbreviate app to a, event to e, and canvas to c for the sake of time. You may assume math and cmu_112_graphics are already imported for you.

Here is a picture of what the app looks like when it first starts:

---

4. Multiple Choice [10 points total]

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


MC1. Which of the following are TRUE statements about the getCellBounds function? List ALL that apply.

A) Also known as the "viewToModel" helper function
B) It takes (app, row, col) returns (x0, y0, x1, y1)
C) We may ONLY call this in redrawAll(app, canvas)
D) We may NEVER call this in redrawAll(app, canvas)
E) This function calls the distance(x0, y0 , x1, y1) helper

MC2. Which of the following is NOT a video we watched in a collab this semester? List ALL that apply.

A) Voting Machine Vulnerabilities
B) Could Deepfakes Weaken Democracy?
C) Biases are Being Baked into Artificial Intelligence
D) "Why Computers Baffle Me"
E) None of the above.

MC3. Which of the following is NOT an MVC Violation? List ALL that apply.

A) Drawing anything in appStarted
B) Setting app.drawAnything to True in appStarted
C) Accessing, but not setting, app.width in redrawAll
D) Setting app.gameOver to True in redrawAll
E) None of the above.

MC4. Which of the following is NOT a rule from the 112 style guide? List ALL that apply.

A) Do not use globals.
B) Do not use magic numbers.
C) Do not exceed 80 characters per line.
D) Do not include any dead code.
E) None of the above.

MC5. Which of the following is the main reason that fasterIsPrime(n) is so much faster than isPrime(n)? Choose one.

A) fasterIsPrime(n) only checks odd numbers, not evens.
B) fasterIsPrime(n) only checks the prime numbers up to n.
C) fasterIsPrime(n) only checks up to the square root of n.
D) fasterIsPrime(n) uses a formula that directly computes whether or not n is prime without using a loop.
E) None of the above.

---

5. Code Tracing [10 points total(5 each)]

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

CT1 (of 2):

def ct1(n):
  s = ''
  for x in range(n, n-4, -1):
    for y in range(n-x):
      s += chr(ord('A') + y + n)
    s += 'x'
  return s


print(ct1(4))

CT2 (of 2):

def ct2(s, t):
  for c in s:
    if (s.count(c) > 1):
      t += c
  while (len(t) > 4):
    t = t[0:-1]
  return t

print(ct2('abbdca', '6'))

---

6. Bonus Fill-in-the-blank [1pt]

The secret word is ________!

---

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

def bonusCt1(n):
  g = c = 0
  while (c < n):
    g += 1
    d, e = 0, g
    while (e > 0):
      d += e%2
      e //= 2
    c += bool(d == n)
  return g
print(bonusCt1(7))

Bonus CT2 of 2

def bonusCt2(x):
  def f(f, g):
    return g(f*g(f))
  def g(f, g):
    return f(g**f(g))
  def h(x):
    return 1 if x<2 else 2*h(x-1)
  def i(x):
    return h(h(x))
  return f(x, h) + g(i, x)
print(bonusCt2(2))

---