Due at 11:59:59 pm on 04/10/2020.

Starter Files

Download lab09.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. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

Trees

Our Tree consists of an entry and a list of its branches. To create a tree and access its root and branches, use the following constructor and selectors:

Constructor
- Tree(entry, branches): creates a tree object with the given root and list of branches. You can also call it with no branches to make a leaf, just like we saw with links.
Selectors
- tree.entry: returns the value of the entry of the tree.
- tree.branches: returns the list of branches of the given tree.
- tree.is_leaf(): returns True if tree's list of branches is empty, and False otherwise. Notice this is a function call

For example, the tree generated by

t = Tree(1, [Tree(2),
             Tree(3, [Tree(4), Tree(5)]),
             Tree(6, [Tree(7)])])

would look like this:

It may be easier to visualize this translation by formatting the code like this:

t = Tree(1,
         [Tree(2),
          Tree(3,
               [Tree(4),
                Tree(5)]),
          Tree(6,
               [Tree(7)])])

To extract the number 3 from this tree, which is the value of the root of its second branch, we would do this:

t.branches[1].entry

Here is the implementation of the tree class, with the __repr__ function giving you what you need to type to create a tree when you enter an instance of the tree into the interpreter, and the __str__ function giving you a pretty version of a tree when you print it.

class Tree:
    def __init__(self, entry, branches=()):
        self.entry = entry
        for branch in branches:
            assert isinstance(branch, Tree)
        self.branches = list(branches)

    def __repr__(self):
        if self.branches:
            branches_str = ', ' + repr(self.branches)
        else:
            branches_str = ''
        return 'Tree({0}{1})'.format(self.entry, branches_str)

    def __str__(self):
        def print_tree(t, indent=0):
            tree_str = '  ' * indent + str(t.entry) + "\n"
            for b in t.branches:
                tree_str += print_tree(b, indent + 1)
            return tree_str
        return print_tree(self).rstrip()

    def is_leaf(self):
        return not self.branches

Below is an example of a type of tree problem you could encounter. We are trying to apply a function onto each value of a tree. There are many steps that are involved in stepping through all the code, but it is most important to understand each part of the function. There are annotations that break down the solution to this problem.

Question 1: WWPP: Trees

Use OK to test your knowledge with the following "What Would Python Print?" questions:
python3 ok -q trees -u
Hint: Remember for all WWPP questions, enter Function if you believe the answer is <function ...> and Error if it errors.

>>> from lab09 import *
>>> t = Tree(1, Tree(2))
______
Error
>>> t = Tree(1, [Tree(2)])
>>> t.entry
______
1
>>> t.branches[0]
______
Tree(2)
>>> t.branches[0].entry
______
2
>>> t.entry = t.branches[0].entry
>>> t
______
Tree(2, [Tree(2)])
>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
______
2
>>> t.branches[0]
______
Tree(2)
>>> t.branches[1]
______
Tree(4, [Tree(8)])

Question 2: Square Tree

Write a function square_tree that mutates a Tree with numerical entries so that each entry is squared.

def square_tree(t):
    """Mutates a Tree t by squaring all its elements.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> square_tree(t)
    >>> t
    Tree(1, [Tree(9, [Tree(25)]), Tree(49)])
    """
    "*** YOUR CODE HERE ***"
    t.entry = t.entry ** 2
    for subtree in t.branches:
        square_tree(subtree)

Use OK to test your code:

python3 ok -q square_tree

Question 3: Leaves

Write a function leaves that returns a list of all the entries of the leaf nodes of a Tree.

def leaves(t):
    """Returns a list of all the entries of the leaf nodes of the Tree t.

    >>> leaves(Tree(1))
    [1]
    >>> leaves(Tree(1, [Tree(2, [Tree(3)]), Tree(4)]))
    [3, 4]
    """
    "*** YOUR CODE HERE ***"
    if t.is_leaf():
        return [t.entry]
    all_leaves = []
    for b in t.branches:
        all_leaves += leaves(b)
    return all_leaves

Use OK to test your code:

python3 ok -q leaves

Question 4: Same Shape

Write a function same_shape that returns True if two Trees have the same shape. Two trees have the same shape if they have the same number of children and each of their children have the same shape.

def same_shape(t1, t2):
    """Returns whether two Trees t1, t2 have the same shape. Two trees have the
    same shape if they have the same number of branches and each of their
    children have the same shape.

    >>> t, s = Tree(1), Tree(3)
    >>> same_shape(t, t)
    True
    >>> same_shape(t, s)
    True
    >>> t = Tree(1, [Tree(2), Tree(3)])
    >>> same_shape(t, s)
    False
    >>> s = Tree(4, [Tree(7)])
    >>> same_shape(t, s)
    False
    >>> s.branches.append(Tree(6)) # Add a new leaf to s to make it same shape as t
    >>> same_shape(t, s)
    True
    """
    "*** YOUR CODE HERE ***"
    return len(t1.branches) == len(t2.branches) and \
        all([same_shape(st1, st2) for st1, st2 in zip(t1.branches, t2.branches)])

Use OK to test your code:

python3 ok -q same_shape

Question 5: 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 ***"
    subtrees = [cumulative_sum(st) for st in t.branches]
    new_entry = sum(st.entry for st in subtrees) + t.entry
    return Tree(new_entry, subtrees)

Use OK to test your code:

python3 ok -q cumulative_sum

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Extra Credit Practice Open in a new window

These questions are new this semester. They're a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88-lab01 for some problems designed to demonstrate how to solve these types of problems.

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

Starting from lab 2 onward, each set of questions are worth half (0.5) a point per lab, for a total opportunity of 4-5 points throughout the semester.

Use OK to test your code:

python3 ok -q extra_credit

Lab 9: Trees

Starter Files

Submission

Trees

Question 1: WWPP: Trees

Question 2: Square Tree

Question 3: Leaves

Question 4: Same Shape

Question 5: Cumulative Sum

Submit

Extra Credit Practice Open in a new window