# CMU 15-112: Fundamentals of Programming and Computer Science Quiz9

See the quiz9 frontmatter. 35 minutes total..

PART 1

SA1 (3 points): If a list L takes 3 seconds to sort using selection sort, how long would we expect the list L*5 to take to sort using selection sort?
• 7 seconds
• 15 seconds
• 25 seconds
• 45 seconds
• 75 seconds
• 225 seconds

SA2 (3 points): If a sorted list L has about 2 billion values in it, how many values would binary search have to check to verify that some value v is not in L?
• 10
• 16
• 21
• 31
• 42
• 64

SA3 (3 points): In the proof that mergesort is O(NlogN), the logN comes from the total number of passes required. Where does the first N in O(NlogN) come from?
• We use L.count(i) in every pass, and L.count(i) requires N steps
• We create 2N sorted sublists in every pass, which simplifies to N
• We perform N comparisons and 2N copies in each step, which simplifies to N
• We use linear search in every pass, which requires N steps
• We add N because we know P == NP for any list of length P, and P == log(N)

SA4, SA5, and SA6 refer to this image of xsortlab. Note that this is selection sort, and it just compared the value at index 5 to the value at index 6. Remember that xsortlab starts indexing at 1 and not 0.

SA4 (2 points): Which pass are we currently on?
• 1st pass
• 3rd pass
• 5th pass
• 14th pass
• 15th pass

SA5 (2 points): What are the indexes of the NEXT two values to be compared?
• 5 and 6
• 5 and 7
• 5 and 14
• 6 and 7
• 6 and 15

SA6 (2 points): What are the indexes of the NEXT two values to be swapped?
• 5 and 6
• 5 and 7
• 5 and 14
• 6 and 14
• 6 and 15

CT1 (10 points):
Indicate what this code prints.

```#Hint: Sets are mutable, so
#   what does u = t create?
def ct1(L):
s = set()
t = set()
for i in range(len(L)):
if L[i]==i: u = t
else:       u = s
return (s, t)
print(ct1([4, 1, 6, 3, 6]))
```

RC1 (10 points):
Find a value for d such that rc1(d) returns True. Put your answer in the blank below, and nothing else.
```def rc1(d):
k = d[0]
c = 1
while k != 0:
k = d[k]
if isinstance(k, int):
c += 100
else:
c += 1
return c == 302
```

PART 2

Free Response 1: busiestStudents(rosters) [35] points]

Background: this problem uses rosters:
```    rosters = {
'15-112':{'amy','bob','claire','dan'},
'18-100':{'amy','claire','john','mark'},
'21-127':{'claire','john','zach'},
'76-101':{'bob','john','margaret'},
}
```
We see that rosters is a dictionary, where each key is the name of a course, and each value is a set of the students in that course.
With that in mind, write the function busiestStudents(rosters) that takes a dictionary of rosters such as the one above (but do not hardcode to that one!), and returns a set of the students who are taking the most courses. In the example above, claire and john are both taking 3 courses, which is the most, so busiestStudents(rosters) returns the set { 'claire', 'john' }.

Hint: it may be helpful if you first create a dictionary mapping each student name to a count of the number of courses that student is taking, but this is just a suggestion.

```def busiestStudents(rosters):
return 42

def testBusiestStudents():
print('Testing busiestStudents()...', end='')
rosters = {
'15-112':{'amy','bob','claire','dan'},
'18-100':{'amy','claire','john','mark'},
'21-127':{'claire','john','zach'},
'76-101':{'bob','john','margaret'},
}
assert(busiestStudents(rosters) == { 'claire', 'john' })
print('Passed!')

testBusiestStudents()
```

Free Response 2: Polynomial class [30] points]

Write the class Polynomial along with the required methods so that the following test function works correctly.
Do not hardcode any test cases.

Hint: Remember from HW9 that methods can return objects. One of the Polynomial methods should return a new Polynomial.
```class Polynomial(object):
def __init__(self, coeffs):  # Complete this method...
pass

# ...and finish writing the rest of the class

def testPolynomialClass():
print('Testing Polynomial class...', end='')
f = Polynomial([2,3,1]) # 2x**2 + 3x + 1
assert(f.evalAt(4) == 2*4**2 + 3*4 + 1) # returns f(4), which is 45
assert(f.evalAt(5) == 2*5**2 + 3*5 + 1) # returns f(5), which is 66
assert(f.getCoefficient(0) == 1) # get the x**0 coefficient
assert(f.getCoefficient(1) == 3) # get the x**1 coefficient
assert(f.getCoefficient(2) == 2) # get the x**2 coefficient
assert(f.getCoefficient(33) == 0) # assume leading 0's...
g = f.times(10) # g is a new polynomial, which is 10*f
# just multiply each coefficient in f by this value
# so g = 20x**2 + 30*x + 10
assert(g.getCoefficient(0) == 10) # get the x**0 coefficient
assert(g.getCoefficient(1) == 30) # get the x**1 coefficient
assert(g.getCoefficient(2) == 20) # get the x**2 coefficient
assert(g.getCoefficient(33) == 0) # assume leading 0's...
assert(g.evalAt(4) == 20*4**2 + 30*4 + 10) # returns g(4), which is 450
print('Passed!')

testPolynomialClass()
```

PART 3

BonusCT1 [+2 points]

This is an optional bonus problem. Indicate what this code prints.
```def bonusCt1(L, s):
L = [chr(ord('a')+L[i]+i) for i in range(len(L))]
s = sorted(set(s) - set(L)) * len(set(s))**len(L)
return ''.join(s).count('rb')
```

BonusCT2 [+2 points]

This is an optional bonus problem. Indicate what this code prints.
```def bonusCt2(m):
def foo(n):
s = set(range(n))
for v in set(str(s)):
if v.isdigit(): s -= {int(v)}
return sum(s)
n = 0
while foo(n) < m: n += 1
return n
print(bonusCt2(42))
```