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

• This lab is Collaborative. No solo work allowed. Work in groups of 2-3 (and the same group the whole time). See the syllabus for more details.
• Starter file: cs112_f16_wk7.py
• This week you may use up to 6 submissions. Only your last submission counts. There is no autograder this week.
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.

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.