Homework 5

Due by 11:59pm on Saturday, 7/18

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 1 for instructions on submitting assignments.

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

Readings: You might find the following references useful:

Mid-semester Survey

Please fill out the mid-semester survey. We appreciate any feedback that you have for us; we want to know what works for you in this class and what doesn't.

Required questions

Question 1: is_sorted

Implement the is_sorted(lst) function, which returns True if the linked list lst is sorted in increasing from left to right. If two adjacent elements are equal, the linked list is still considered sorted.

def is_sorted(lst):
    """Returns True if the linked list is sorted.

    >>> lst1 = link(1, link(2, link(3, link(4))))
    >>> is_sorted(lst1)
    True
    >>> lst2 = link(1, link(3, link(2, link(4, link(5)))))
    >>> is_sorted(lst2)
    False
    >>> lst3 = link(3, link(3, link(3)))
    >>> is_sorted(lst3)
    True
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q is_sorted

Question 2: Interleave

Write interleave(s0, s1), which takes two linked lists and produces a new linked list with elements of s0 and s1 interleaved. In other words, the resulting list should have the first element of the s0, the first element of s1, the second element of s0, the second element of s1, and so on.

If the two lists are not the same length, then the leftover elements of the longer list should still appear at the end.

def interleave(s0, s1):
    """Interleave linked lists s0 and s1 to produce a new linked
    list.

    >>> evens = link(2, link(4, link(6, link(8, empty))))
    >>> odds = link(1, link(3, empty))
    >>> print_link(interleave(odds, evens))
    1 2 3 4 6 8
    >>> print_link(interleave(evens, odds))
    2 1 4 3 6 8
    >>> print_link(interleave(odds, odds))
    1 1 3 3
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q interleave

Question 3: Height

Define the function height, which takes in a tree as an argument and returns the number of branches it takes start at the root node and reach the leaf that is farthest away from the root.

Note: given the definition of the height of a tree, if height is given a leaf, what should it return?

def height(t):
    """Return the depth of the deepest node in the tree.

    >>> height(tree(1))
    0
    >>> height(tree(1, [tree(2), tree(3)]))
    1
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> height(numbers)
    2
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q height

Question 4: Sprout leaves

Define a function sprout_leaves that, given a tree, t, and a list of values, vals, and produces a tree with every leaf having new children that contain each of the items in vals. Do not add new children to non-leaf nodes.

def sprout_leaves(t, vals):
    """Sprout new leaves containing the data in vals at each leaf in
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q sprout_leaves