#
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 u.add(L[i]) 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') print(bonusCt1([2, -1], 'abracadabra'))

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