CMU 15-112: Fundamentals of Programming and Computer Science

See the quiz9 frontmatter. 35 minutes total..


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?

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?

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?

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?

SA5 (2 points): What are the indexes of the NEXT two values to be compared?

SA6 (2 points): What are the indexes of the NEXT two values to be swapped?

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
            c += 1
    return c == 302


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

Background: this problem uses rosters:
    rosters = {
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 = {
    assert(busiestStudents(rosters) == { 'claire', 'john' })


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

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



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