More important notes:
- For any tech fails, follow instructions at the top of this page
- 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!
0. TA-led mini-lectures [10 points]
If you attended the entirety of a TA-led term project mini-lecture, these 10 points are yours. No need to write anything for this. :]
1. Free Response: Big-Oh [25 points]
The following function f(L) runs in O(N**2), where len(L) == N. Write the function g(L) that behaves identically to f(L) only g(L) runs in O(N). Assume that L is a non-empty list of integers.
def f(L):
total = count = 0
for i in range(len(L)):
v = L[i]
M = L[i+1:]
if (v not in M):
total += v
count += 1
return total/count
2. Free Response: Objects [25 points]
You are given this code:
from dataclasses import make_dataclass
Dot = make_dataclass('Dot', ['position', 'isBlue'])
This defines the Dot class, where a Dot has two values, an (x,y)
position and a boolean value isBlue indicating whether or not
the dot is blue.With this in mind, write the function makeCenteredDot(dot1, dot2) that takes two Dot instances and returns a third Dot instance that is positioned at the midpoint between dot1 and dot2, and is blue if and only if dot1 and dot2 have the same color. (Assume dots can only be blue or red.)
Here are some test cases for you:
dot1 = Dot( position=(0, 0), isBlue=True ) dot2 = Dot( position=(2, 2), isBlue=False) # The new position is at (1, 1), which is the midpoint between # (0, 0) and (2, 2). Also, the new dot is not blue because # dot1 and dot2 do not have the same color. dot3 = Dot( position=(1, 1), isBlue=False) assert(makeCenteredDot(dot1, dot2) == dot3) dot1 = Dot( position=(4, 2), isBlue=False ) dot2 = Dot( position=(0, 0), isBlue=False ) # The new position is at (2, 1), which is the midpoint between # (4, 2) and (0, 0). Also, the new dot is blue because # dot1 and dot2 have the same color. dot3 = Dot( position=(2, 1), isBlue=True ) assert(makeCenteredDot(dot1, dot2) == dot3)
3. Short Answers [40 points total]
Clearly write your answers next to the problem number for each question, and circle them!
SA1. Arrange the following 6 function families in order from smallest to largest:
N N**0.5 2**N logN 1 N**2
SA2. Say you have a profoundly large list L such that binary search would have to make 81 comparisons to verify that a value v is not in L. Then you do this:
M = sorted(L * 1000)To the nearest integer, how many comparisons would binary search have to make to verify that v is not in M?
SA3. If f(N) runs in O(N**3), and f(2000) takes 2 seconds, how long would f(6000) take?
SA4. If f(2000) takes 2 seconds, and f(6000) takes 7 seconds, what is the most likely function family that f runs in?
SA5. Indicate ALL that are TRUE about mergesort:
A) mergesort runs in O(NlogN)SA6. The following is a snapshot of xSortLab running selectionSort. What are the indexes of the next two values to be swapped?
B) mergesort requires O(N) passes
C) on each pass, mergesort does O(logN) steps
D) mergesort uses more space than selectionsort, since mergesort uses an extra "auxiliary" list and selectionsort does not
E) mergesort is generally much faster than selectionsort
SA7. The following is a snapshot of xSortLab running mergeSort. What are the indexes of the next two values to be compared?
SA8. Fill in the blank:
def selectionSort(a):
n = len(a)
for startIndex in range(n):
minIndex = startIndex
for i in range(startIndex+1, n):
if (a[i] < a[minIndex]):
minIndex = i
_________________________ # <-- HERE
4. Bonus Code Tracing [Up to 2 points]
What does the following code print?
Be certain to show your work, and also very clearly circle your answer!
Bonus CT 1 (of 1)
def bonusCt(n):
M = [ ]
while len(M) < 4:
M.append(n % 19)
n += 2
if (n // M[-1] == 2**M[-1]):
M.append(sum(M)//2**n + 1)
M.append(M[0]-sum(M))
s = 'b'
d = ord(s)
for dd in M[2:]+M[:2]:
d += dd
s += chr(d)
if (len(s) == 2):
s += ' '
return s + '!!!'
print(bonusCt(18))