Due by 11:59pm on Monday, 3/28

Instructions

Download hw05.zip. Inside the archive, you will find a file called hw05.py, along with a copy of the OK autograder.

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. See Lab 0 for instructions on submitting assignments.

Using OK: If you have any questions about using OK, please refer to this guide.

Assorted Problems You've Seen Before

The following problems were extra from this week's lab. If you've already done them, feel free to re-use your solutions.

Question 1: Cumulative Sum

Write a function cumulative_sum that returns a new Tree, where each entry is the sum of all entries in the corresponding subtree of the old Tree.

def cumulative_sum(t):
    """Return a new Tree, where each entry is the sum of all entries in the
    corresponding subtree of t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative = cumulative_sum(t)
    >>> t
    Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative
    Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
    >>> cumulative_sum(Tree(1))
    Tree(1)
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q cumulative_sum

Question 2: Link to List

Write a function link_to_list that converts a given Link to a Python list.

def link_to_list(link):
    """Takes a Link and returns a Python list with the same elements.

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> link_to_list(link)
    [1, 2, 3, 4]
    >>> link_to_list(Link.empty)
    []
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q link_to_list

Question 3: Reverse

Implement reverse, which takes a linked list link and returns a linked list containing the elements of link in reverse order. The original link should be unchanged.

def reverse(link):
    """Returns a Link that is the reverse of the original.

    >>> print_link(reverse(Link(1)))
    <1>
    >>> link = Link(1, Link(2, Link(3)))
    >>> new = reverse(link)
    >>> print_link(new)
    <3 2 1>
    >>> print_link(link)
    <1 2 3>
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q reverse

Question 4: Cycles

The Link class can represent lists with cycles. That is, a list may contain itself as a sublist.

>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3

Implement has_cycle,that returns whether its argument, a Link instance, contains a cycle.

Hint: Iterate through the linked list and try keeping track of which Link objects you've already seen.

def has_cycle(link):
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle(t)
    False
    >>> u = Link(2, Link(2, Link(2)))
    >>> has_cycle(u)
    False
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q has_cycle

Extra for experts: Implement has_cycle with only constant space. (If you followed the hint above, you will use linear space.) The solution is short (less than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

def has_cycle_constant(link):
    """Return whether link contains a cycle.

    >>> s = Link(1, Link(2, Link(3)))
    >>> s.rest.rest.rest = s
    >>> has_cycle_constant(s)
    True
    >>> t = Link(1, Link(2, Link(3)))
    >>> has_cycle_constant(t)
    False
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q has_cycle_constant

Binary Search Trees

The following problems deal with binary trees, in which each node has at most two children. We further modify the definition of tree to allow empty trees, which we haven't dealt with up to now. So here, we define a binary tree as either

  • An empty tree, or
  • A label and two children, called the left and right child respectively, both of which are binary trees. The left and right children, therefore, are the roots of the left and right subtrees.

As a result of this definition, most recursion on binary trees uses the empty tree as a base case.

Our implementation of binary trees is the following:

# Tree definition
class BinTree:
    empty = ()

    def __init__(self, label, left=empty, right=empty):
        self.label = label
        self.left = left
        self.right = right

    def __repr__(self):
        if self.left == self.empty and self.right == self.empty:
            return 'BinTree({})'.format(repr(self.label))
        left = 'BinTree.empty' if self.left == self.empty else repr(self.left)
        right = 'BinTree.empty' if self.right == self.empty else repr(self.right)
        return 'BinTree({}, {}, {})'.format(repr(self.label), left, right)

def binTree(tupleTree):
    """A convenience method for succinctly constructing binary trees.  The
    empty tuple or list stands for BinTree.empty; (V,) or [V] stands
    for BinTree(V); (V, T1, T2) or [V, T1, T2] stands for
    BinTree(V, binTree(T1), binTree(T2)).
    >>> binTree((3,
    ...          (1, (), [2]),
    ...          (6, [5], [7])))
    BinTree(3, BinTree(1, BinTree.empty, BinTree(2)), BinTree(6, BinTree(5), BinTree(7)))
    """
    if len(tupleTree) == 0:
        return BinTree.empty
    elif len(tupleTree) == 1:
        return BinTree(tupleTree[0])
    else:
        return BinTree(tupleTree[0], binTree(tupleTree[1]), binTree(tupleTree[2]))

We also included a function print_bintree, which prints out a string representation of a tree:

>>> print_bintree(binTree( (1, (3, (), [2]), (4, [5], [6])) ))
 -1-
/   \
3   4
 \ / \
 2 5 6

A binary search tree (or BST) is a binary tree that obeys the following constraint:

  • All labels in the left subtree have a value less than or equal to the label of v, and
  • All labels in the right subtree have a value greater than or equal to the label of v.
  • This is true for its children subtree and their grandchildren (and so on) as well.

Thus, these are BSTs:

              --4--          1               4         4
             /     \          \             /         /
            2       6          2           3         1
           / \     /            \         /           \
          1   3   5              3       2             3
                                  \     /             / 
                                   4   1             2

These are binary trees, but not BSTs:

              --6--          4      
             /     \          \     
            2       4          3    
           / \     /            \   
          1   3   5              2  
                                  \ 
                                   1

Question 5: Min

Define the function bst_min, which takes in a binary search tree and returns the min of all of the labels of its nodes. Be sure to take advantage of the properties of the binary search tree to get an efficient solution.

You may assume the input is a non-empty BinTree.

def bst_min(b):
    r""" Returns the min of all the values of each node in b.

    Calling bst_min on the following tree should return 1:

            4
           / \
          2   6
         /   /
        1   5

    >>> t1 = binTree([4, [2, [1], []], [6, [5], []]])
    >>> bst_min(t1)
    1
    >>> t2 = binTree([4])
    >>> bst_min(t2)
    4
    >>> t3 = binTree([4, [2], []])
    >>> bst_min(t3)
    2
    >>> t4 = binTree([4, [], [6]])
    >>> bst_min(t4)
    4
    >>> t5 = binTree([9, [6, [5], [7]], []])
    >>> bst_min(t5)
    5
    >>> # Illegal BST, but if your solution is right, it should NOT
    >>> # print 100.
    >>> t6 = binTree([9, [6, [5], [7]], [-100]])
    >>> bst_min(t6)
    5
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q bst_min

Question 6: Max

Define the function bst_max, which takes in a binary search tree and returns the max of all of the labels of its nodes. Be sure to take advantage of the properties of the binary search tree to get an efficient solution.

You may assume the input is a non-empty BinTree.

def bst_max(b):
    r""" Returns the max of all the labels in B, assuming B is a BST.

    Calling bst_max on the following tree should return 6:

            4
           / \
          2   6
         /   /
        1   5

    >>> t1 = binTree([4, [2, [1], []], [6, [5], []]])
    >>> bst_max(t1)
    6
    >>> t2 = binTree([4])
    >>> bst_max(t2)
    4
    >>> t3 = binTree([4, [2], []])
    >>> bst_max(t3)
    4
    >>> t4 = binTree([4, [], [6]])
    >>> bst_max(t4)
    6
    >>> t5 = binTree([4, [], [6, [5], [7]]])
    >>> bst_max(t5)
    7
    >>> # Illegal BST, but if your solution is right, it should NOT
    >>> # print 100.
    >>> t6 = binTree([4, [100], [6, [5], [7]]])
    >>> bst_max(t6)
    7
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q bst_max

Question 7: is_valid

Write a function is_valid_bst, which takes a given binary tree and returns True iff that tree is a valid binary search tree. That is, for every node, the labels in that node's left children are less than the label of the node, and the labels of its right children are greater than that of the node. You might find the bst_min and bst_max functions helpful.

def is_valid_bst(bst):
    """
    >>> t1 = binTree([4, [2, [1], []], [6, [5], []]])
    >>> is_valid_bst(t1)
    True
    >>> t2 = binTree([4, [100], [6, [5], [7]]])
    >>> is_valid_bst(t2)
    False
    >>> t3 = binTree([6, [5, [3, [1], [4]], [7]], [8, [7], [9]]])
    >>> is_valid_bst(t3)
    False
    >>> t4 = binTree([1])
    >>> is_valid_bst(t4)
    True
    >>> t5 = binTree([6, [5, [3, [4], [1]], []], [8, [7], [9]]])
    >>> is_valid_bst(t5)
    False
    >>> is_valid_bst(BinTree.empty)
    True
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q is_valid_bst

Python Sets

A set is an unordered collection of distinct objects that supports membership testing, union, intersection, and adjunction. The main difference between sets and lists are 1. they are unordered, and 2. there are no duplicates. Other than that almost everything is the same.

>>> a = [1, 1, 2, 2, 3, 3]
>>> a = set(a)
>>> a  # No duplicates
{1, 2, 3}
>>> a = {3, 1, 2}
>>> a  # Not necessarily in same order
{1, 2, 3}

The Python documentation on sets has more details. One really convenient thing about Python sets is that many operations on sets (adding elements, removing elements, checking membership) run in O(1) (constant) time (usually).

Some of the problems use a utility method called timeit, which takes a parameterless function as argument, executes it, and returns the time required to do so. It's a variation on the function timeit.timeit function in the Python3 library.

Question 8: Add up

Write the following function so it (usually) runs in O(m) time, where m is the length of lst.

def add_up(n, lst):
    """Returns True if any two non identical elements in lst add up to 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
    >>> add_up(151, range(0, 200000, 2))
    False
    >>> timeit(lambda: add_up(151, range(0, 200000, 2))) < 1.0
    True
    >>> add_up(50002, range(0, 200000, 2))
    True
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q add_up

Question 9: Missing value

Write the following function so it (usually) runs in O(n) time, where n is the length of lst0.

def missing_val(lst0, lst1):
    """Assuming that LST0 contains all the values in LST1, but LST1 is missing
    one value in LST0, return the missing value.  The values need not be
    numbers.

    >>> from random import shuffle
    >>> missing_val(range(10), [1, 0, 4, 5, 7, 9, 2, 6, 3])
    8
    >>> big0 = [str(k) for k in range(15000)]
    >>> big1 = [str(k) for k in range(15000) if k != 293 ]
    >>> shuffle(big0)
    >>> shuffle(big1)
    >>> missing_val(big0, big1)
    '293'
    >>> timeit(lambda: missing_val(big0, big1)) < 1.0
    True
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q missing_val