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:
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
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 ***"
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.
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 ***"
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 ***"
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 ***"
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 ***"
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 ***"
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 ***"
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 ***"