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.

Efficiency

Recall that the order of growth of a function expresses how long it takes for the function to run, and is defined in terms of the function's input sizes.

For example, let's say that we have the function get_x which is defined as follows:

def get_x(x):
    return x

get_x has one expression in it. That one expression takes the same amount of time to run, no matter what x is, or more importantly, how large x gets. This is called constant time, or O(1).

The main two ways that a function in your program will get a running time different than just constant time is through either iteration or recursion. Let's start with some iteration examples!

The (simple) way you figure out the running time of a particular while loop is to simply count the cost of each operation in the body of the while loop, and then multiply that cost by the number of times that the loop runs. For example, look at the following method with a loop in it:

def foo(n):
    i = 1
    sum = 0
    while i <= n:
        sum = sum + i
        i = i + 1
    return sum

This loop has two statements in it sum = sum + i and i = i + 1. Each statement is a constant time operation, since the amount of time each statement takes does not depend on the input to the function n. In C88C, we are not concerned with how long primitive functions such as addition, multiplication, and variable assignment take to run. Rather we are concerned with how many more times a loop is executed or how many more recursive calls occur as the input increases. In this example, we execute the loop n times, and for each iteration, we only execute constant time operations, so we get an order of growth of O(n).

Here are a couple of basic functions, along with their running times. Try to understand why they have the given running time.

O(n)

def bar(n):
    i = 1
    a = 1
    b = 0
    while i <= n:
        temp = a
        a = a + b
        b = temp
        i = i + 1
    return a

O(n^2)

def bar(n):
    sum = 0
    a, b = 0, 0
    while a < n:
        while b < n:
            sum += (a*b)
            b += 1
        b = 0
        a += 1
    return sum

There is nothing to submit for this part. But doing these problems will be good practice. The solutions are given right below the question and to see them you must highlight them.

Question 1

What is the asymptotic run time of the baz function.

def baz(n):
    i = 1
    sum = 0
    while i <= n:
        sum += bam(i)
        i += 1
    return sum

def bam(n):
    i = 1
    sum = 0
    while i <= n:
        sum += i
        i += 1
    return sum

Highlight the text on the line below this line to see the solution:
Answer: O(n²)).

Question 2

def bonk(n):
    sum = 0
    while n >= 2:
        sum += n
        n = n / 2
    return sum

Highlight the text on the line below this line to see the solution:
Answer: O(log(n)).

Trees

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

• Constructor

  • Tree(value, branches): creates a tree object with the given root and list of branches.
  • Tree(value): creates a tree object with no branches to make a leaf, similar to what we saw with linked lists.

• Selectors

  • tree.value: returns the value of the root 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:

   1
 / | \
2  3  6
  / \  \
 4   5  7

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].value

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, value, branches=()):
        self.value = value
        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.value, branches_str)

    def __str__(self):
        def print_tree(t, indent=0):
            tree_str = '  ' * indent + str(t.value) + "\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

Question 3: Search

Write a function search that returns the Tree, whose root node is the given value if it exists and None if it does not. You can assume all values are unique.

def search(t, value):
    """Searches for and returns the Tree whose value is equal to value if
    it exists and None if it does not. Assume unique values.

    >>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> search(t, 10)
    >>> search(t, 5)
    Tree(5)
    >>> search(t, 1)
    Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
    >>> search(t, 7)
    Tree(7)
    """
    "*** YOUR CODE HERE ***"
    if t.value == value:
        return t
    for branch in t.branches:
        result = search(branch, value)
        if result is not None:
            return result
    return

Toggle Solution

Use OK to test your code:

python3 ok -q search

Question 4: Cumulative Sum

Write a function cumulative_sum that returns a new Tree, where each value is the sum of all values in the corresponding subtree of the old Tree.

def cumulative_sum(t):
    """Return a new Tree, where each value is the sum of all values 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_value = sum(st.value for st in subtrees) + t.value
    return Tree(new_value, subtrees)

Toggle Solution

Use OK to test your code:

python3 ok -q cumulative_sum

Question 5: Add Leaves

Implement add_d_leaves, a function that takes in a Tree instance t and mutates it so that at each depth d in the tree, d leaves with labels v are added to each node at that depth. For example, we want to add 1 leaf with v in it to each node at depth 1, 2 leaves to each node at depth 2, and so on.

Recall that the depth of a node is the number of edges from that node to the root, so the depth of the root is 0. The leaves should be added to the end of the list of branches.

def add_d_leaves(t, v):
    """Add d leaves containing v to each node at every depth d.

    >>> t1 = Tree(1, [Tree(3)])
    >>> add_d_leaves(t1, 4)
    >>> t1
    Tree(1, [Tree(3, [Tree(4)])])
    >>> t2 = Tree(2, [Tree(5), Tree(6)])
    >>> t3 = Tree(3, [t1, Tree(0), t2])
    >>> add_d_leaves(t3, 10)
    >>> print(t3)
    3
      1
        3
          4
            10
            10
            10
          10
          10
        10
      0
        10
      2
        5
          10
          10
        6
          10
          10
        10
    """
    def add_leaves(t, d):
        "*** YOUR CODE HERE ***"
        for b in t.branches:
            add_leaves(b, d + 1)
        t.branches.extend([Tree(v) for _ in range(d)])
    add_leaves(t, 0)

Toggle Solution

Use OK to test your code:

python3 ok -q add_d_leaves

Exceptions

Exceptions allow us to try a chunk of code, and then catch any errors that might come up. If we do catch an exception, we can run an alternative set of instructions. This construct is very useful in many situations.

try:
    <try suite>
except Exception as e:
    <except suite>
else:
    <else suite>
finally:
    <finally suite>

Notice that we can catch the exception as e. This binds the name e to the exception object. This can be helpful when we want to give extra information on what happened. For example, we can print(e) inside the except clause.

Also, we have an optional else case. The else suite is executed if the try suite finishes without any exceptions.

We also have an optional finally clause, which is always executed, whether or not an exception is thrown. We generally don't need to use the else and finally controls in this class.

When we write exception statements, we generally don't just use the class Exception as above. Rather, we figure out the specific type of exception that we want to handle, such as TypeError or ZeroDivisionError. To figure out which type of exception you are trying to handle, you can type purposely wrong things into the interpreter (such as 'hi' + 5 or 1 / 0) and see what kind of exception Python spits out.

Question 6: No KeyErrors Allowed

If we try to look up a key that does not exist in a dictionary, then Python will raise a KeyError. Write the function avoid_keyerror which returns the value mapped to key in the dictionary. If key does not exist, print 'Avoid Exception' and set key to the string 'no value'.

def avoid_keyerror(dictionary, key):
    """ Returns the value associated with key in dictionary. If key 
    does not exist in the dictionary, print out 'Avoid Exception' and
    map it to the string 'no value'.

    >>> d = {1: 'one', 3: 'three', 5: 'five'}
    >>> avoid_keyerror(d, 3)
    'three'
    >>> avoid_keyerror(d, 4)
    Avoid Exception
    >>> d[4]
    'no value'
    """
    "*** YOUR CODE HERE ***"
    
    try:
        return dictionary[key]
    except KeyError as e:
        print("Avoid Exception")
        dictionary[key] = 'no value'

Toggle Solution

Use OK to test your code:

python3 ok -q avoid_keyerror

Submission

When you are done, submit your file to Gradescope. You only need to upload the following files:

• lab09.py

You may submit more than once before the deadline; only the final submission will be graded. It is your responsibility to check that the autograder on Gradescope runs as expected after you upload your submission.