Switch to Pensieve:

• Everyone: Go to pensieve.co, log in with your @berkeley.edu email, and enter your group number (which was in the email that assigned you to this lab).

Once you're on Pensieve, you don't need to return to this page; Pensieve has all the same content (but more features). If for some reason Penseive doesn't work, return to this page and continue with the discussion.

Getting Started

Everyone go around and say your name.

For fun: Think of a big word with at least three syllables, such as "solitary" or "conundrum" or "ominous". Try to use it as many times as you can during today's discussion, but in ways that don't give away that it's your big word. At the end, your group will try to guess each person's big word. Whoever uses their big word the most times (and at least twice) without their group guessing it wins. (You win nothing; it's just a game.)

To get help from a TA, If you do not have an in-person TA, you can reach your TA using this Zoom link.

If there are fewer than 3 people in your group, feel free to merge your group with another group in the room.

Trees

For a tree t:

• Its root label can be any value, and label(t) returns it.
• Its branches are trees, and branches(t) returns a list of branches.
• An identical tree can be constructed with tree(label(t), branches(t)).
• You can call functions that take trees as arguments, such as is_leaf(t).
• That's how you work with trees. No t == x or t[0] or x in t or list(t), etc.
• There's no way to change a tree (that doesn't violate an abstraction barrier).

Here's an example tree t1, for which its branch branches(t1)[1] is t2.

t2 = tree(5, [tree(6), tree(7)])
t1 = tree(3, [tree(4), t2])

A path is a sequence of trees in which each is the parent of the next.

def tree(label, branches=[]):
    for branch in branches:
        assert is_tree(branch), 'branches must be trees'
    return [label] + list(branches)

def label(tree):
    return tree[0]

def branches(tree):
    return tree[1:]

def is_leaf(tree):
    return not branches(tree)

def is_tree(tree):
    if type(tree) != list or len(tree) < 1:
        return False
    for branch in branches(tree):
        if not is_tree(branch):
            return False
    return True

Q1: Warm Up

What value is bound to result?

result = label(min(branches(max([t1, t2], key=label)), key=label))

How convoluted! (That's a big word.)

>>> s = [-3, -5, -4, -1, -2]
>>> max(s)
-1
>>> max(s, key=abs)
-5
>>> max([abs(x) for x in s])
5

In case you're wondering, this expression does not violate an abstraction barrier. [t1, t2] and branches(t) are both lists (not trees), and so it's fine to call min and max on them.

Q2: Has Path

Implement has_path, which takes a tree t and a list p. It returns whether there is a path from the root of t with labels p. For example, t1 has a path from its root with labels [3, 5, 6] but not [3, 4, 6] or [5, 6].

Important: Before trying to implement this function, discuss these questions from lecture about the recursive call of a tree processing function:

• What recursive calls will you make?
• What type of values do they return?
• What do the possible return values mean?
• How can you use those return values to complete your implementation?

If you get stuck, you can view our answers to these questions by clicking the hint button below, but please don't do that until your whole group agrees.

def has_path(t, p):
    """Return whether tree t has a path from the root with labels p.

    >>> t2 = tree(5, [tree(6), tree(7)])
    >>> t1 = tree(3, [tree(4), t2])
    >>> has_path(t1, [5, 6])        # This path is not from the root of t1
    False
    >>> has_path(t2, [5, 6])        # This path is from the root of t2
    True
    >>> has_path(t1, [3, 5])        # This path does not go to a leaf, but that's ok
    True
    >>> has_path(t1, [3, 5, 6])     # This path goes to a leaf
    True
    >>> has_path(t1, [3, 4, 5, 6])  # There is no path with these labels
    False
    """
    if p == [label(t)]:
        return True
    elif label(t) != p[0]:
        return False
    else:
        return any([has_path(b, p[1:]) for b in branches(t)])

        for b in branches(t):
            if has_path(b, p[1:]):
                return True
        return False

If your group needs some guidance, you can click on the hints below, but please talk with your group first before reading the hints.

for ____:
    if ____:
        return True
return False

New Rule: Whoever in your group helped type the answer to the last question should not type the answer to the next one. Instead, just ask questions and give suggestions; give other members of your group a chance to type the answer.

Q3: Find Path

Implement find_path, which takes a tree t with unique labels and a value x. It returns a list containing the labels of the nodes along a path from the root of t to a node labeled x.

If x is not a label in t, return None. Assume that the labels of t are unique.

First talk through how to make and use the recursive call. (Try it yourselves; don't just click the hint button. That's how you learn.)

def find_path(t, x):
    """
    >>> t2 = tree(5, [tree(6), tree(7)])
    >>> t1 = tree(3, [tree(4), t2])
    >>> find_path(t1, 5)
    [3, 5]
    >>> find_path(t1, 4)
    [3, 4]
    >>> find_path(t1, 6)
    [3, 5, 6]
    >>> find_path(t2, 6)
    [5, 6]
    >>> print(find_path(t1, 2))
    None
    """
    if label(t) == x:
        return [label(t)]
    for b in branches(t):
        path = find_path(b, x)
        if path:
            return [label(t)] + path
    return None

Please don't view the hints until you've discussed with your group and can't make progress.

Description Time! When your group has completed this question, it's time to describe why this function does not have a base case that uses is_leaf. Come up with an explanation as a group, pick someone to present your answer, and then tell your TA (on Zoom if your TA is remote).

Document the Occasion

For each person, the rest of the group should try to guess their big word (from the Getting Started section). The group only gets one guess. After they guess, reveal your big word and how many times you used it during discussion.

Please all fill out the attendance form (one submission per person per week).