*Due at 11:59pm on 03/19/2015.*

Download lab08.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

By the end of this lab, you should have submitted the lab with
`python3 ok --submit`

. You may submit more than once before the
deadline; only the final submission will be graded.

- To receive credit for this lab, you must complete questions 1-5 in lab08.py and submit through OK.
- Questions 6-10 are
*extra practice*. They can be found in the lab08_extra.py file. It is recommended that you complete these problems on your own time.

`slice_link`

that slices a given Link. `slice_link`

should slice the Link starting at `start`

and ending one element before
`end`

, as with a normal Python list.
```
def slice_link(link, start, end):
"""Slices a Link from start to end (as with a normal Python list).
>>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
>>> slice_link(link, 1, 4)
Link(1, Link(4, Link(1)))
"""
"*** YOUR CODE HERE ***"
if end == 0:
return Link.empty
elif start == 0:
return Link(link.first, slice_link(link.rest, 0, end-1))
else:
return slice_link(link.rest, start-1, end-1)
```

A set is an unordered collection of distinct objects that supports membership testing, union, intersection, and adjunction:

Construction

`>>> empty = set() # construct an empty set >>> s = {3, 2, 1, 4, 4} >>> s {1, 2, 3, 4}`

Adjunction:

`>>> s.add(5) >>> s {1, 2, 3, 4, 5}`

Operations

`>>> 3 in s True >>> 7 not in s True >>> len(s) 5 >>> s.union({1, 5}) {1, 2, 3, 4, 5} >>> s.intersection({6, 5, 4, 3}) {3, 4, 5}`

For more detail on Sets you can go to this link

Implement the union function for sets. Union takes in two sets, and returns a new set with elements from the first set, and all other elements that have not already have been seen in the second set.

```
def union(s1, s2):
"""Returns the union of two sets.
>>> r = {0, 6, 6}
>>> s = {1, 2, 3, 4}
>>> t = union(s, {1, 6})
>>> t
{1, 2, 3, 4, 6}
>>> union(r, t)
{0, 1, 2, 3, 4, 6}
"""
"*** YOUR CODE HERE ***"
union_set = set()
for elem in s1:
union_set.add(elem)
for elem in s2:
union_set.add(elem)
return union_set
```

Implement the intersection function for two sets. Intersection takes in two sets and returns a new set of only the elements in both sets.

```
def intersection(s1, s2):
"""Returns the intersection of two sets.
>>> r = {0, 1, 4, 0}
>>> s = {1, 2, 3, 4}
>>> t = intersection(s, {3, 4, 2})
>>> t
{2, 3, 4}
>>> intersection(r, t)
{4}
"""
"*** YOUR CODE HERE ***"
intersection_set = set()
for elem in s1:
if elem in s2:
intersection_set.add(elem)
return intersection_set
```

Write the following function so it runs in O(n) time.

```
def extra_elem(a,b):
"""B contains every element in A, and has one additional member, find
the additional member.
>>> extra_elem(['dog', 'cat', 'monkey'], ['dog', 'cat', 'monkey', 'giraffe'])
'giraffe'
>>> extra_elem([1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6])
6
"""
"*** YOUR CODE HERE ***"
return list(set(b) - set(a))[0]
```

Write the following function so it runs in O(n) time.

```
def find_duplicates(lst):
"""Returns True if lst has any duplicates and False if it does not.
>>> find_duplicates([1, 2, 3, 4, 5])
False
>>> find_duplicates([1, 2, 3, 4, 2])
True
"""
"*** YOUR CODE HERE ***"
return len(set(lst)) != len(lst)
```

The following questions are for **extra practice** — they can be found
in the lab08_extra.py file. It is recommended that
you complete these problems on your own time.

Write the following function so it runs in O(n) time.

```
def add_up(n, lst):
"""Returns True if any two non identical elements in lst add up to any n.
>>> add_up(100, [1, 2, 3, 4, 5])
False
>>> add_up(7, [1, 2, 3, 4, 2])
True
>>> add_up(10, [5, 5])
False
"""
"*** YOUR CODE HERE ***"
check_set = set()
for elem in lst:
if n - elem != elem:
check_set.add(n - elem)
return bool(intersection(check_set, set(lst)))
```

Write the following function so it runs in O(log n) time.

```
def pow(n,k):
"""Computes n^k.
>>> pow(2, 3)
8
>>> pow(4, 2)
16
"""
"*** YOUR CODE HERE ***"
if k == 1:
return n
if k % 2 == 0:
return pow(n*n,k//2)
else:
return n * pow(n*n, k//2)
```

Write the following function so it runs in O(n) time.

```
def missing_no(lst):
"""lst contains all the numbers from 1 to n for some n except some
number k. Find k.
>>> missing_no([1, 0, 4, 5, 7, 9, 2, 6, 3])
8
>>> missing_no(list(filter(lambda x: x != 293, list(range(2000)))))
293
"""
"*** YOUR CODE HERE ***"
return sum(range(max(lst) + 1)) - sum(lst)
```

Write the following function so it runs in O(n) time.

```
def find_duplicates_k(k, lst):
"""Returns True if there are any duplicates in lst that are within k
indices apart.
>>> find_duplicates_k(3, [1, 2, 3, 4, 1])
False
>>> find_duplicates_k(4, [1, 2, 3, 4, 1])
True
"""
"*** YOUR CODE HERE ***"
prev_set = set()
for i, elem in enumerate(lst):
if elem in prev_set:
return True
prev_set.add(elem)
if i - k >= 0:
prev_set.remove(lst[i - k])
return False
```

Write the following function so it runs in O(n) time.

```
def find_duplicates_k_l(k, l, lst):
"""Returns True if there are any two values who in lst that are within k
indices apart AND if the absolute value of their difference is less than
or equal to l.
>>> find_duplicates_k_l(4, 0, [1, 2, 3, 4, 5])
False
>>> find_duplicates_k_l(4, 1, [1, 2, 3, 4, 5])
True
>>> find_duplicates_k_l(4, 0, [1, 2, 3, 4, 1])
True
>>> find_duplicates_k_l(2, 0, [1, 2, 3, 4, 1])
False
>>> find_duplicates_k_l(1, 100, [100, 275, 320, 988, 27])
True
>>> find_duplicates_k_l(1, 100, [100, 199, 275, 320, 988, 27])
True
>>> find_duplicates_k_l(1, 100, [100, 23, 199, 275, 320, 988, 27])
True
>>> find_duplicates_k_l(2, 100, [100, 23, 199, 275, 320, 988, 27])
True
"""
"*** YOUR CODE HERE ***"
```