CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science
Lab 7 (Due Thursday 13-Oct, at 10pm, no extensions or grace days)



  1. 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 prove (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
    

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

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