#
CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science

Lab 7 (Due Thursday 12-Oct, at 10pm)

- 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. Be sure to list your collaboration partners (name and andrew id) in a comment on the first line of your submitted file. - Even though this is collaborative, you may not directly copy any code from anyone, and you may not electronically share your code with anyone.
- Be a good lab partner! Help everyone in your lab group, and accept their help if you need it. Don't be in a hurry to finish the problems. Instead, take your time and be sure that everyone in the lab group is following and understanding. The goal is to learn, not just to finish.
- Starter files: No starter files this week.
- You should make use of this week's linter: cs112_f17_week7_linter.py
- 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.

**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.**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 justify (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. Your solution should be more efficient.**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.