CS61A: Lecture 22

Lecture

Tree Class

• A Tree has a label and a list of branches; each branch is also a Tree

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

• This style of object-based abstraction is highly similar to the functional abstraction we have defined prior. However, the definition is much shorter and the implementation is nearly identical.
• Ex: Generate a fibonacci Tree

def fib_tree(n):
    if n < 2:
        return Tree(n)
    else:
        left = fib_tree(n-2)
        right = fib_tree(n-1)
        fib_n = left.label + right.label
        return Tree(fib_n, [left, right])

<__main__.Tree at 0x7f2c7030e860>

from treeclass import Tree

• Ex: Count Twins
  • Implement twins, which takes a Tree t. It returns the number of pairs of sibling nodes whose labels are equal.

def twins(t):
    """Count the pairs of sibling nodes with equal labels.

    >>> t1 = Tree(3, [Tree(4, [Tree(5), Tree(6)]), Tree(4, [Tree(5), Tree(5)])])
    >>> twins(t1) # 4 and 5
    2
    >>> twins(Tree(1, [Tree(1, [Tree(2)]), Tree(2, [Tree(2)])]))
    0
    >>> twins(Tree(8,[t1,t1,t1]))
    9
    """
    count = 0
    n = len(t.branches)
    for i in range(n-1):
        for j in range(i+1, n):
            if t.branches[i].label == t.branches[j].label:
                count += 1
    return count + sum([twins(b) for b in t.branches])

t1 = Tree(3, [Tree(4, [Tree(5), Tree(6)]), Tree(4, [Tree(5), Tree(5)])])
twins(Tree(8,[t1,t1,t1]))

9

• Spring 2023 Midterm 2 Question 4(b) You have already implemented exclude(t, x), which takes a Tree instance t and a value x. It returns a Tree containing the root node of t as well as each non-root node of t with a label not equal to x. The parent of a node in the result is its nearest ancestor node that is not excluded. The input t is not modified.

Implement remove, which takes a Tree instance t and a value x. It removes all non-root nodes from t that have a label equal to x, then returns t. The parent of a node in t is its nearest ancestor that is not removed. You may call exclude.

def exclude(t, x):
    return Tree(t.label, sum([[exclude(b, x)] for b in t.branches if b.label != x else [exclude(b1, x) for b1 in b.branches]], []))

def remove(t, x):
    t.branches = exclude(t, x).branches
    return t

u = Tree(1, [Tree(2, [Tree(2), Tree(3)]), Tree(4)])
remove(u)

Efficiency

• It is really inefficient to implement the calculation of the fibonacci sequence using tree recursion.
  • This is because each call to fib recursively creates many duplicate calls that dramatically speeds up our execution time

class CallCounter:
    def __init__(self):
        self.n = 0

    def count(self, f):
        def counted(n):
            self.n+=1
            return f(n)
        return counted

fib_counter = CallCounter()
@fib_counter.count
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

fib(5)
fib_counter.n

15

Memoization

• A simple technique to speed up this process is to remember the results that have been computed before. This is called memoization

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

def memo(f):
    cache = {}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized

fib_counter = CallCounter()
fib = memo(fib)
fib = fib_counter.count(fib)
fib(7)
fib_counter.n

13

• The memo function serves to cache the previous inputs that we’ve had to reuse them when necessary.
  • If our inputs happens to be an unhashable type such as a List, then we would either need to represent it as something that is hashable, or come up with another way of memoizing our results. (Hint hint DFS on a 2D array of array indices)

Orders of Growth

• We measure efficiency of computer programs in Orders of Growth.
  • However, this measure is not specific to each program as execution time may vary by different machines.
  • We instead generalize different algorithms in accordance to how much their resource consumption scales as input size grows
• Orders of Growth for an input-size n:
  • Exponential growth:
    • Ex: Recursive fib
    • Incrementing n multiplies time by a constant.
    • Typically Tree recursive algorithms have this characteristic, unless we memoize.
  • Quadratic growth.
    • Incrementing n increases time by n times a constant.
    • The amount of time added at each increment gets bigger and bigger, but not as much as exponential.
  • Linear growth.
    • Incrementing n increases time by a constant.
    • This is typically what memoization helps us achieve.
  • Logarithmic growth.
    • Really, really useful is n is large.
    • Doubling n only increments time by a constant.
  • Constant growth.
    • Increasing n doesn’t affect time.
• Ex: What is the order of growth of the time to run prefix(s) in terms of the length of s?

def prefix(s):
    t = 0
    result = []
    for x in s:
        t = t + x
        result.append(t)
    return result

• We would have a linear time, as we add a constant to our time with every increment to our input size.