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

**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:- State in just a few words what it does in general.
- State and prove (in a few words) its worst-case big-oh runtime.
- 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!
- State and prove (in a few words) your better solution's worst-case big-oh runtime.

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

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