# CS 61A Lab 7

## Starter Files

We've provided a set of starter files with skeleton code for the exercises in the lab. You can get them in the following places:

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

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

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

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

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

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

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

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

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

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