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

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

2. 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 justify (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
# 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
```