Lab 8: Linked Lists and Sets

Due at 11:59pm on 03/19/2015.

Starter Files

Download lab08.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded.

Table of Contents

Linked Lists

Question 1

Implement a function slice_link that slices a given Link. slice_link should slice the Link starting at start and ending one element before end, as with a normal Python list.
def slice_link(link, start, end):
    """Slices a Link from start to end (as with a normal Python list).

    >>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
    >>> slice_link(link, 1, 4)
    Link(1, Link(4, Link(1)))
    """
"*** YOUR CODE HERE ***"
if end == 0: return Link.empty elif start == 0: return Link(link.first, slice_link(link.rest, 0, end-1)) else: return slice_link(link.rest, start-1, end-1)

Sets

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

For more detail on Sets you can go to this link

Question 2

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 ***"
union_set = set() for elem in s1: union_set.add(elem) for elem in s2: union_set.add(elem) return union_set

Question 3

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 ***"
intersection_set = set() for elem in s1: if elem in s2: intersection_set.add(elem) return intersection_set

Question 4

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

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

Extra Questions

The following questions are for extra practice — they can be found in the lab08_extra.py file. It is recommended that you complete these problems on your own time.

Question 6

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

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
    """
"*** YOUR CODE HERE ***"
if k == 1: return n if k % 2 == 0: return pow(n*n,k//2) else: return n * pow(n*n, k//2)

Question 8

Write the following function so it runs in O(n) time.

def missing_no(lst):
    """lst contains all the numbers from 1 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 ***"
return sum(range(max(lst) + 1)) - sum(lst)

Question 9

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

Question 10: 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 ***"