CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 9 (Due Thursday 23-Mar, at 10pm)

---

This lab has 2 required forms -- one to make groups and one to peer-review each others' groupwork (in terms of being great groupmates, not in terms of getting right answers).

• Group Formation Form: Due Tuesday 11:59pm [2.5 pts]
  Fill out one of the following forms:
  • If you already have a group, fill out this form (one per group!)
  • If you need a new group, fill out this form
  Once you submit one of these forms your group is final for the lab unless your group members are unresponsive, in which case you should email Eddie (edryer).


• Group Peer-Review Form: Due Thursday 11:59pm [2.5 pts]
  Fill out this peer review form once for each member of your group.

---

• 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 files: No starter files this week.
• This week you may use up to 5 submissions. Only your last submission counts.
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.
• As usual, there are no late days for this lab.

---

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.