# CS 61A Lab 7

## Sets & Orders of Growth

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

### Sets

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}
``````

``````>>> 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}
"""
``````

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}
"""
``````

### Orders of Growth

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

>>> extra_elem(['dog', 'cat', 'monkey'], ['dog', 'cat', 'monkey', 'giraffe'])
'giraffe'
>>> extra_elem([1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6])
6
"""
``````

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
False
"""
``````

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
"""
``````

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
"""
``````

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
"""
``````

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
"""
``````

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
"""