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:

• lab7.py

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}

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

def union(s1,s2):
    union_set = set()
    for elem in s1:
        union_set.add(elem)
    for elem in s2:
        union_set.add(elem)
    return union_set

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

def intersection(s1, s2):
    intersection_set = set()
    for elem in s1:
        if elem in s2:
            intersection_set.add(elem)
    return intersection_set

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

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
    """
    return list(set(b) - set(a))[0]

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

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
    """
    check_set = set()
    for elem in lst:
        if n - elem != elem:
            check_set.add(n - elem)
    return bool(intersection(check_set, set(lst)))

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

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
    """
    return len(set(lst)) != len(lst)

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

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

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

def pow(n,k):
    """Computes n^k.

    >>> pow(2, 3)
    8
    >>> pow(4, 2)
    16
    """
    if k == 1:
        return n
    if k % 2 == 0:
        return pow(n*n,k//2)
    else:
        return n * pow(n*n, k//2)

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

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
    """
    return sum(range(max(lst) + 1)) - sum(lst)

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