Lab 8 Solutions

Solution Files

Topics

Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.


Mutable Trees

A Tree instance has two instance attributes:

  • label is the value stored at the root of the tree.
  • branches is a list of Tree instances that hold the labels in the rest of the tree.

The Tree class (with its __repr__ and __str__ methods omitted) is defined as:

class Tree:
    """
    >>> t = Tree(3, [Tree(2, [Tree(5)]), Tree(4)])
    >>> t.label
    3
    >>> t.branches[0].label
    2
    >>> t.branches[1].is_leaf()
    True
    """
    def __init__(self, label, branches=[]):
        for b in branches:
            assert isinstance(b, Tree)
        self.label = label
        self.branches = list(branches)

    def is_leaf(self):
        return not self.branches

To construct a Tree instance from a label x (any value) and a list of branches bs (a list of Tree instances) and give it the name t, write t = Tree(x, bs).

For a tree t:

  • Its root label can be any value, and t.label evaluates to it.
  • Its branches are always Tree instances, and t.branches evaluates to the list of its branches.
  • t.is_leaf() returns True if t.branches is empty and False otherwise.
  • To construct a leaf with label x, write Tree(x).

Displaying a tree t:

  • repr(t) returns a Python expression that evaluates to an equivalent tree.
  • str(t) returns one line for each label indented once more than its parent with children below their parents.
>>> t = Tree(3, [Tree(1, [Tree(4), Tree(1)]), Tree(5, [Tree(9)])])

>>> t         # displays the contents of repr(t)
Tree(3, [Tree(1, [Tree(4), Tree(1)]), Tree(5, [Tree(9)])])

>>> print(t)  # displays the contents of str(t)
3
  1
    4
    1
  5
    9

Changing (also known as mutating) a tree t:

  • t.label = y changes the root label of t to y (any value).
  • t.branches = ns changes the branches of t to ns (a list of Tree instances).
  • Mutation of t.branches will change t. For example, t.branches.append(Tree(y)) will add a leaf labeled y as the right-most branch.
  • Mutation of any branch in t will change t. For example, t.branches[0].label = y will change the root label of the left-most branch to y.
>>> t.label = 3.0
>>> t.branches[1].label = 5.0
>>> t.branches.append(Tree(2, [Tree(6)]))
>>> print(t)
3.0
  1
    4
    1
  5.0
    9
  2
    6

Here is a summary of the differences between the tree data abstraction implemented as a functional abstraction vs. implemented as a class:

- Tree constructor and selector functions Tree class
Constructing a tree To construct a tree given a label and a list of branches, we call tree(label, branches) To construct a tree object given a label and a list of branches, we call Tree(label, branches) (which calls the Tree.__init__ method).
Label and branches To get the label or branches of a tree t, we call label(t) or branches(t) respectively To get the label or branches of a tree t, we access the instance attributes t.label or t.branches respectively.
Mutability The functional tree data abstraction is immutable (without violating its abstraction barrier) because we cannot assign values to call expressions The label and branches attributes of a Tree instance can be reassigned, mutating the tree.
Checking if a tree is a leaf To check whether a tree t is a leaf, we call the function is_leaf(t) To check whether a tree t is a leaf, we call the method t.is_leaf(). This method can only be called on Tree objects.

Linked Lists

A linked list is a data structure for storing a sequence of values. It is more efficient than a regular built-in list for certain operations, such as inserting a value in the middle of a long list. Linked lists are not built in, and so we define a class called Link to represent them. A linked list is either a Link instance or Link.empty (which represents an empty linked list).

A instance of Link has two instance attributes, first and rest.

The rest attribute of a Link instance should always be a linked list: either another Link instance or Link.empty. It SHOULD NEVER be None.

To check if a linked list is empty, compare it to Link.empty. Since there is only ever one empty list, we can use is to compare, but == would work too.

def is_empty(s):
    """Return whether linked list s is empty."""
    return s is Link.empty:

You can mutate a Link object s in two ways:

  • Change the first element with s.first = ...
  • Change the rest of the elements with s.rest = ...

You can make a new Link object by calling Link:

  • Link(4) makes a linked list of length 1 containing 4.
  • Link(4, s) makes a linked list that starts with 4 followed by the elements of linked list s.

Required Questions


Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Mutable Trees

Q1: WWPD: Trees

Read over the Tree class in lab08.py. Make sure you understand the doctests.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q trees-wwpd -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed. Recall that Tree instances will be displayed the same way they are constructed.

>>> t = Tree(1, Tree(2))

______
Error

>>> t = Tree(1, [Tree(2)])
>>> t.label

______
1

>>> t.branches[0]

______
Tree(2)

>>> t.branches[0].label

______
2

>>> t.label = t.branches[0].label
>>> 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)])

Q2: Cumulative Mul

Write a function cumulative_mul that mutates the Tree t so that each node's label is replaced by the product of its label and the labels of all its descendents.

Hint: Be careful of the order in which you mutate the current node's label and process its subtrees; which one should come first?

def cumulative_mul(t):
    """Mutates t so that each node's label becomes the product of its own
    label and all labels in the corresponding subtree rooted at t.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> cumulative_mul(t)
    >>> t
    Tree(105, [Tree(15, [Tree(5)]), Tree(7)])
    >>> otherTree = Tree(2, [Tree(1, [Tree(3), Tree(4), Tree(5)]), Tree(6, [Tree(7)])])
    >>> cumulative_mul(otherTree)
    >>> otherTree
    Tree(5040, [Tree(60, [Tree(3), Tree(4), Tree(5)]), Tree(42, [Tree(7)])])
    """

    for b in t.branches:
        cumulative_mul(b)
    total = t.label
    for b in t.branches:
        total *= b.label
    t.label = total

# Alternate solution using only one loop
def cumulative_mul(t):
    for b in t.branches:
        cumulative_mul(b)
        t.label *= b.label

Use Ok to test your code:

python3 ok -q cumulative_mul

Q3: Delete

Implement delete, which takes a Tree t and removes all non-root nodes labeled x. The parent of each remaining node is its nearest ancestor that was not removed. The root node is never removed, even if its label is x.

def delete(t, x):
    """Remove all nodes labeled x below the root within Tree t. When a non-leaf
    node is deleted, the deleted node's children become children of its parent.

    The root node will never be removed.

    >>> t = Tree(3, [Tree(2, [Tree(2), Tree(2)]), Tree(2), Tree(2, [Tree(2, [Tree(2), Tree(2)])])])
    >>> delete(t, 2)
    >>> t
    Tree(3)
    >>> t = Tree(1, [Tree(2, [Tree(4, [Tree(2)]), Tree(5)]), Tree(3, [Tree(6), Tree(2)]), Tree(4)])
    >>> delete(t, 2)
    >>> t
    Tree(1, [Tree(4), Tree(5), Tree(3, [Tree(6)]), Tree(4)])
    >>> t = Tree(1, [Tree(2, [Tree(4), Tree(5)]), Tree(3, [Tree(6), Tree(2)]), Tree(2, [Tree(6),  Tree(2), Tree(7), Tree(8)]), Tree(4)])
    >>> delete(t, 2)
    >>> t
    Tree(1, [Tree(4), Tree(5), Tree(3, [Tree(6)]), Tree(6), Tree(7), Tree(8), Tree(4)])
    """
    new_branches = []

    for b in t.branches:
        delete(b, x)
        if b.label == x:

            new_branches.extend(b.branches)
        else:

            new_branches.append(b)
    t.branches = new_branches

Use Ok to test your code:

python3 ok -q delete

Linked Lists

Q4: WWPD: Linked Lists

Read over the Link class. Make sure you understand the doctests.

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q link -u

Enter Function if you believe the answer is <function ...>, Error if it errors, and Nothing if nothing is displayed.

If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the Link class into the interpreter with python3 -i lab08.py.

>>> link = Link(1000)
>>> link.first

______
1000

>>> link.rest is Link.empty

______
True

>>> link = Link(1000, 2000)

______
AssertionError

>>> link = Link(1000, Link())

______
TypeError
>>> link = Link(1, Link(2, Link(3)))
>>> link.first

______
1

>>> link.rest.first

______
2

>>> link.rest.rest.rest is Link.empty

______
True

>>> link.first = 9001
>>> link.first

______
9001

>>> link.rest = link.rest.rest
>>> link.rest.first

______
3

>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest is Link.empty

______
False

>>> link.rest.rest.rest.rest.first

______
1

>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first

______
1

>>> link2.rest.first

______
2
>>> link = Link(5, Link(6, Link(7)))
>>> link                 # Look at the __repr__ method of Link

______
Link(5, Link(6, Link(7)))

>>> print(link)          # Look at the __str__ method of Link

______
<5 6 7>

Write a function convert_link that takes in a linked list and returns the sequence as a Python list. You may assume that the input list is shallow; none of its elements are themselves another linked list.

Try to find both an iterative and recursive solution for this problem!

Challenge (Optional): Do NOT assume that the input list is shallow (i.e. your input can be a nested linked list). Hint: use the built-in type function.

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

    >>> link = Link(1, Link(2, Link(3, Link(4))))
    >>> lst = convert_link(link)
    >>> lst
    [1, 2, 3, 4]
    >>> convert_link(Link.empty)
    []
    """

    # Recursive solution
    if link is Link.empty:
        return []
    return [link.first] + convert_link(link.rest)

# Iterative solution
def convert_link_iterative(link):
    result = []
    while link is not Link.empty:
        result.append(link.first)
        link = link.rest
    return result

# Challenge solution
def convert_link_challenge(link):
    if link is Link.empty:
        return []
    if type(link.first) == Link:
        return [convert_link_challenge(link.first)] + convert_link_challenge(link.rest)
    return [link.first] + convert_link_challenge(link.rest)
Video Walkthrough:

YouTube link

Use Ok to test your code:

python3 ok -q convert_link

Walkthrough:

YouTube link

Write a function add_link that takes in two linked lists, link1 and link2, and returns a new linked list that concatenates link2 to the end of link1.

You may assume that the input list is shallow; none of its elements are themselves another linked list.

Note: You may not assume that the input lists are of the same length.

Challenge (Optional): Do NOT assume that the input list is shallow (i.e. your input can be a nested linked list). Hint: use the built-in type function.

def add_links(link1, link2):
    """Adds two Links, returning a new Link

    >>> l1 = Link(1, Link(2))
    >>> l2 = Link(3, Link(4, Link(5)))
    >>> new = add_links(l1, l2)
    >>> print(new)
    <1 2 3 4 5>
    >>> new2 = add_links(l2,l1)
    >>> print(new2)
    <3 4 5 1 2>
    """

    if link1 is not Link.empty:
        return Link(link1.first, add_links(link1.rest, link2))
    elif link2 is not Link.empty:
        return Link(link2.first, add_links(link1, link2.rest))
    else:
        return Link.empty

# Iterative version (using reverse)
def add_links(link1, link2):
    result = Link.empty
    while link1 is not Link.empty:
        result = Link(link1.first, result)
        link1 = link1.rest
    while link2 is not Link.empty:
        result = Link(link2.first, result)
        link2 = link2.rest
    return reverse(result)

Use Ok to test your code:

python3 ok -q add_links

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

In addition, all students who are not in the mega lab must submit the attendance form for credit. Ask your section TA for the link! Submit this form for each section, whether you attended lab or missed it for a good reason. The attendance form is not required for mega section students.

Optional Questions

Write a function that takes in a Python list of linked lists and multiplies them element-wise. It should return a new linked list.

If not all of the Link objects are of equal length, return a linked list whose length is that of the shortest linked list given. You may assume the Link objects are shallow linked lists, and that lst_of_lnks contains at least one linked list.

Hint: Use the provided doctests to understand what happens when the linked lists are different lengths. Could this serve as a base case?

def multiply_lnks(lst_of_lnks):
    """
    >>> a = Link(2, Link(3))
    >>> b = Link(5, Link(4))
    >>> p1 = multiply_lnks([a, b])
    >>> p1
    Link(10, Link(12))

    >>> c = Link(2, Link(3, Link(5)))
    >>> d = Link(6, Link(4, Link(2)))
    >>> e = Link(4, Link(1, Link(0, Link(2))))
    >>> p2 = multiply_lnks([c, d, e])
    >>> p2
    Link(48, Link(12, Link(0)))
    """
    product = 1

    for lnk in lst_of_lnks:
        if lnk is Link.empty:
            return Link.empty
        product *= lnk.first
    lst_of_lnks_rests = [lnk.rest for lnk in lst_of_lnks]
    return Link(product, multiply_lnks(lst_of_lnks_rests))

Use Ok to test your code:

python3 ok -q multiply_lnks