We've provided a starter file with skeleton code for the exercises in the lab. You can get it at the following link:

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

Construction

```
>>> 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 the following link: PythonSets

**Problem 1**: 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 ***"
```

**Problem 2**: 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 ***"
```

One really convenient thing about sets is that many operations on sets (adding elements, removing elements, checking membership) run in O(1) (constant) time. If you are interested on how, look up HashSets or look at the third challenge problem here.

**Problem 3**: 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 ***"
```

**Problem 4**: 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 ***"
```

**Problem 5**: 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 ***"
```

**Problem 6**: 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 ***"
```

**Problem 7**: 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 ***"
```

**Problem 8**: Write the following function so it runs in O(n) time.

```
def missing_no(lst):
"""lst contains all the numbers from 0 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 ***"
```

**Problem 9 Extra for Experts**: 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 ***"
```