CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 7 (Due Thursday 12-Oct, at 10pm)



  1. Group Form [5 pts]:
    Fill out one form found here. This is due Thursday by 11:59pm. Even if you work on the lab alone (which you shouldn't do), you should still fill out the form, and simply enter your name without any partner scores.

    If you need a new group, fill out this form to be assigned to one.

  2. Better Big Oh [50 pts] [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. State and justify (in a few words) its worst-case big-oh runtime.
    3. Provide an equivalent Python function that is more than a constant-factor faster (so it's worst-case big-oh runtime is in a different function family). The better your solution's big-oh runtime, the more points you get!
    4. State and prove (in a few words) your better solution's worst-case big-oh runtime.
    You should assume that lists all contain at least 5 values, and only integer values. Also, if a function takes two lists, you should assume they are the same length N.
    import copy
    
    def slow1(a):
        (b, c) = (copy.copy(a), 0)
        while (b != [ ]):
            b.pop()
            c += 1
        return c
    
    def slow2(a):
        n = len(a)
        count = 0
        for i in range(n):
            for j in range(n):
                if (a[i] == a[j]):
                    count += 1
        return (count == n)
    
    def slow3(a, b):
        # assume a and b are the same length n
        n = len(a)
        assert(n == len(b))
        result = 0
        for c in b:
            if c not in a:
                result += 1
        return result 
    
    def slow4(a, b):
        # assume a and b are the same length n
        n = len(a)
        assert(n == len(b))
        result = abs(a[0] - b[0])
        for c in a:
            for d in b:
                delta = abs(c - d)
                if (delta > result):
                    result = delta
        return result
    
    def slow5(a, b):
        # Hint: this is a tricky one!  Even though it looks syntactically
        # almost identical to the previous problem, in fact the solution
        # is very different and more complicated.
        # You'll want to sort one of the lists,
        # and then use binary search over that sorted list (for each value in
        # the other list).  In fact, you should use bisect.bisect for this
        # (you can read about this function in the online Python documentation).
        # The bisect function returns the index i at which you would insert the
        # value to keep the list sorted (with a couple edge cases to consider, such
        # as if the value is less than or greater than all the values in the list, 
        # or if the value actually occurs in the list).
        # The rest is left to you...
        #
        # assume a and b are the same length n
        n = len(a)
        assert(n == len(b))
        result = abs(a[0] - b[0])
        for c in a:
            for d in b:
                delta = abs(c - d)
                if (delta < result):
                    result = delta
        return result
    

  3. largestSumOfPairs(a) [25 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.

    The naive solution is to try every possible pair of numbers in the list. This runs in O(n**2) time and is much too slow. Your solution should be more efficient.

  4. containsPythagoreanTriple(a) [20 pts] [autograded]
    Write the function containsPythagoreanTriple(a) that takes a list of positive integers and returns True if there are 3 values (a,b,c) anywhere in the list such that (a,b,c) form a Pythagorean Triple (where a**2 + b**2 == c**2). So [1,3,6,2,5,1,4] returns True because of (3,4,5).

    A naive solution would be to check every possible triple (a,b,c) in the list. That runs in O(n**3). You'll have to do better than that.