CMU 15-112 Summer 2018: Fundamentals of Programming and Computer Science
Homework 9 (Due Tue 12-Jun, at 5pm)

  1. Big-O Calculation [36pts] [manually graded]
    In a triple-quoted string at the top of your file (just below your name), include solutions to this exercise. For each of the following functions:

    1. State in just a few words what it does in general.
    2. Write the Big-O time or number of loops for each line of the program, then state the resulting Big-O of the whole program.
    3. Provide an equivalent Python function that is more than a constant-factor faster (so its worst-case Big-O runtime is in a different function family). The better your solution's Big-O runtime, the more points you get!
    4. Write the Big-O time or number of loops for each line of the new program, then state the resulting Big-O of the whole program.

    def slow1(lst): # N is the length of the list lst
        assert(len(lst) >= 2)
        a = lst.pop()
        b = lst.pop(0)
        lst.insert(0, a)
    def slow2(lst): # N is the length of the list lst
        counter = 0
        for i in range(len(lst)):
            if lst[i] not in lst[:i]:
                counter += 1
        return counter
    import string
    def slow3(s): # N is the length of the string s
        maxLetter = ""
        maxCount = 0
        for c in s:
            for letter in string.ascii_lowercase:
                if c == letter:
                    if s.count(c) > maxCount or \
                       s.count(c) == maxCount and c < maxLetter:
                        maxCount = s.count(c)
                        maxLetter = c
        return maxLetter

  2. invertDictionary(d) [40 pts] [autograded]
    Write the function invertDictionary(d) that takes a dictionary d that maps keys to values and returns a dictionary of its inverse, that maps the original values back to their keys. One complication: there can be duplicate values in the original dictionary. That is, there can be keys k1 and k2 such that (d[k1] == v) and (d[k2] == v) for the same value v. For this reason, we will in fact map values back to the set of keys that originally mapped to them. So, for example:
    assert(invertDictionary({1:2, 2:3, 3:4, 5:3}) ==
           {2:set([1]), 3:set([2,5]), 4:set([3])})
    Also, you may assume that the values in the original dictionary are all immutable, so that they are legal keys in the resulting inverted dictionary.

  3. largestSumOfPairs(a) [24 pts] [autograded]
    Write the function largestSumOfPairs(a) that takes a list of integers, and returns the largest sum of any two elements in that list, or None if the list is of size 1 or smaller. So, largestSumOfPairs([8,4,2,8]) returns the largest of (8+4), (8+2), (8+8), (4+2), (4+8), and (2+8), or 16.

    Note on runtime: Your function must run in O(n) time. The brute force solution is to try every possible pair of numbers in the list. This runs in O(n**2) time and is much too slow. Another solution might involve sorting. Sorting runs in O(nlogn) times and is also too slow.

    Note on autograding: The autograder will sometimes tell you your solution is too slow. However it may not catch all solutions that are too slow (particularly ones that sort using builtins). The running time of your code will be checked manually after the deadline by TAs.