Due at 11:59pm on Friday, 07/13/2018.

Lab Check-in 4 questions here.

Starter Files

Download lab06.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.

• Questions 1-3 must be completed in order to receive credit for this lab. Starter code for problems 2 and 3 is in lab06.py.
• Question 4-15 are midterm review problems, and are optional. It is recommended that you try these problems in your own time. Starter code for problems 6-13 are in lab06_extra.py.

Note: In order to help you prepare for the midterm, solutions to the problems in this lab assignment will be released on Sunday, July 11. You may consult them if you get stuck or to check your answers, but remember that it would be most beneficial to spend some time trying out the problems first. You must still submit the required questions by the due date if you want to receive credit for this lab assignment.

The construct_check module is used in this assignment, which defines a function check. For example, a call such as

check("foo.py", "func1", ["While", "For", "Recursion"])

checks that the function func1 in file foo.py does not contain any while or for constructs, and is not an overtly recursive function (i.e., one in which a function contains a call to itself by name.)

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.

Trees

A tree is a data structure that represents a hierarchy of information. A file system is a good example of a tree structure. For example, within your cs61a folder, you have folders separating your projects, lab assignments, and homework. The next level is folders that separate different assignments, hw01, lab01, hog, etc., and inside those are the files themselves, including the starter files and ok. Below is an incomplete diagram of what your cs61a directory might look like.

As you can see, unlike trees in nature, the tree abstract data type is drawn with the root at the top and the leaves at the bottom.

Some tree terminology:

• root: the node at the top of the tree
• label: the value in a node, selected by the label function
• branches: a list of trees directly under the tree's root, selected by the branches function
• leaf: a tree with zero branches
• node: any location within the tree (e.g., root node, leaf nodes, etc.)

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

• Constructor

  • tree(label, branches=[]): creates a tree object with the given label value at its root node and list of branches. Notice that the second argument to this constructor, branches, is optional - if you want to make a tree with no branches, leave this argument empty.

• Selectors

  • label(tree): returns the value in the root node of tree.
  • branches(tree): returns the list of branches of the given tree.

• Convenience function

  • is_leaf(tree): returns True if tree's list of branches is empty, and False otherwise.

For example, the tree generated by

number_tree = 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

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

label(branches(number_tree)[1])

The print_tree function prints out a tree in a human-readable form. The exact form follows the pattern illustrated above, where the root is unindented, and each of its branches is indented one level further.

def print_tree(t, indent=0):
    """Print a representation of this tree in which each node is
    indented by two spaces times its depth from the root.

    >>> print_tree(tree(1))
    1
    >>> print_tree(tree(1, [tree(2)]))
    1
      2
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    """
    print('  ' * indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent + 1)

Required Questions

Tree Practice

Q1: WWPD: Trees

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

python3 ok -q trees -u

Type Error if the code errors and Nothing if nothing is displayed. Draw out the tree on the board or a piece of paper if you get stuck!

>>> from lab06 import *
>>> t = tree(1, tree(2))
______
Error
>>> t = tree(1, [tree(2)])
______
Nothing
>>> label(t)
______
1
>>> label(branches(t)[0])
______
2
>>> x = branches(t)
>>> len(x)
______
1
>>> is_leaf(x[0])
______
True
>>> branch = x[0]
>>> label(t) + label(branch)
______
3
>>> len(branches(branch))
______
0

>>> from lab06 import *
>>> b1 = tree(5, [tree(6), tree(7)])
>>> b2 = tree(8, [tree(9, [tree(10)])])
>>> t = tree(11, [b1, b2])
>>> for b in branches(t):
...     print(label(b))
______
5
8
>>> for b in branches(t):
...     print(is_leaf(branches(b)[0]))
...
______
True
False
>>> [label(b) + 100 for b in branches(t)]
______
[105, 108]
>>> [label(b) * label(branches(b)[0]) for b in branches(t)]
______
[30, 72]

Q2: Acorn Finder

The squirrels on campus need your help! There are a lot of trees on campus and the squirrels would like to know which ones contain acorns. Define the function acorn_finder, which takes in a tree and returns True if the tree contains a node with the value 'acorn' and False otherwise.

def acorn_finder(t):
    """Returns True if t contains a node with the value 'acorn' and
    False otherwise.

    >>> scrat = tree('acorn')
    >>> acorn_finder(scrat)
    True
    >>> sproul = tree('roots', [tree('branch1', [tree('leaf'), tree('acorn')]), tree('branch2')])
    >>> acorn_finder(sproul)
    True
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> acorn_finder(numbers)
    False
    """
    "*** YOUR CODE HERE ***"
    if label(t) == 'acorn':
        return True
    for b in branches(t):
        if acorn_finder(b):
            return True
    return False

# Alternative solution
def acorn_finder(t):
    if label(t) == 'acorn':
        return True
    return True in [acorn_finder(b) for b in branches(t)]

Use Ok to test your code:

python3 ok -q acorn_finder

Q3: Sprout leaves

Define a function sprout_leaves that takes in a tree, t, and a list of values, vals. It produces a new tree that is identical to t, but where each old leaf node has new branches, one for each value in vals.

For example, say we have the tree t = tree(1, [tree(2), tree(3, [tree(4)])]):

  1
 / \
2   3
    |
    4

If we call sprout_leaves(t, [5, 6]), the result is the following tree:

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

def sprout_leaves(t, vals):
    """Sprout new leaves containing the data in vals at each leaf in
    the original tree t and return the resulting tree.

    >>> t1 = tree(1, [tree(2), tree(3)])
    >>> print_tree(t1)
    1
      2
      3
    >>> new1 = sprout_leaves(t1, [4, 5])
    >>> print_tree(new1)
    1
      2
        4
        5
      3
        4
        5

    >>> t2 = tree(1, [tree(2, [tree(3)])])
    >>> print_tree(t2)
    1
      2
        3
    >>> new2 = sprout_leaves(t2, [6, 1, 2])
    >>> print_tree(new2)
    1
      2
        3
          6
          1
          2
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t):
        return tree(label(t), [tree(v) for v in vals])
    return tree(label(t), [sprout_leaves(s, vals) for s in branches(t)])

Use Ok to test your code:

python3 ok -q sprout_leaves

Optional Questions: Midterm Review

Note: Do not feel obligated to do all of these problems. These are here primarily to help you prepare for the midterm, so we advise prioritizing the topics you want the most practice with and/or the problems you feel might be most helpful, as well as looking under those topics in our Resources tab.

Functions

Q4: WWPD: Call Expressions

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

python3 ok -q call_expressions -u

For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

>>> from operator import add
>>> def double(x):
...     return x + x
>>> def square(y):
...     return y * y
>>> def f(z):
...     add(square(double(z)), 1)
>>> f(4)
______
Nothing

>>> def foo(x, y):  
...     print("x or y")  
...     return x or y  
>>> a = foo  
______
Nothing  
>>> b = foo()  
______
Error  
>>> c = a(print("x"), print("y"))  
______
x  
y  
x or y  
>>> print(c)  
______
None

>>> def welcome():
...     print('welcome to')
...     return 'hello'
>>> def cs61a():
...     print('cs61a')
...     return 'world'
>>> print(welcome(), cs61a())
______
welcome to
cs61a
hello world

Higher-Order Functions

Q5: Doge

Draw the environment diagram for the following code.

wow = 6

def much(wow):
    if much == wow:
        such = lambda wow: 5
        def wow():
            return such
        return wow
    such = lambda wow: 4
    return wow()

wow = much(much(much))(wow)

You can check out what happens when you run the code block using Python Tutor.

Recursion

Q6: Interleaved Sum

Recall that the summation function computes the sum of a sequence of terms from 1 to n:

def summation(n, term):
    """Return the sum of the first n terms of a sequence.

    >>> summation(5, lambda x: pow(x, 3))
    225
    """
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total

Write a function interleaved_sum that similarly computes the sum of a sequence of terms from 1 to n, but uses different functions to compute the terms for odd and even numbers. Do so without using any loops or testing in any way if a number is odd or even.

Hint: You can test if a number is equal to 0, 1, or n. If you start summing from the term 1, you'll be able to tell whether the current term is odd or even. How can you keep track of an extra variable for the current term in a recursive function?

def interleaved_sum(n, odd_term, even_term):
    """Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
    to n.

    >>> # 1 + 2^2 + 3 + 4^2 + 5
    ... interleaved_sum(5, lambda x: x, lambda x: x*x)
    29
    >>> from construct_check import check
    >>> check(LAB_SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod'])
    True
    """
    "*** YOUR CODE HERE ***"
    def interleaved_helper(term0, term1, k):
        if k == n:
            return term0(k)
        return term0(k) + interleaved_helper(term1, term0, k+1)
    return interleaved_helper(odd_term, even_term, 1)

# Alternate solution
def interleaved_sum2(n, odd_term, even_term):
    """Compute the sum odd_term(1) + even_term(2) + odd_term(3) + ..., up
    to n.

    >>> # 1 + 2^2 + 3 + 4^2 + 5
    ... interleaved_sum2(5, lambda x: x, lambda x: x*x)
    29
    """
    total, term0, term1 = interleaved_helper2(n, odd_term, even_term)
    return total

def interleaved_helper2(n, odd_term, even_term):
    if n == 1:
        return odd_term(1), even_term, odd_term
    else:
        total, term0, term1 = interleaved_helper2(n-1, odd_term, even_term)
        return total + term0(n), term1, term0

# Alternate solution using odd_term and even_term separately
def interleaved_sum3(n, odd_term, even_term):
    def interleaved_helper3(i, fn):
        if i > n:
            return 0
        return fn(i) + interleaved_helper3(i + 2, fn)
    return interleaved_helper3(0, even_term) + interleaved_helper3(1, odd_term)

Use Ok to test your code:

python3 ok -q interleaved_sum

Tree Recursion

Q7: Insect Combinatorics

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal. (There is a closed-form solution to this problem, but try to answer it procedurally using recursion.)

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

def paths(m, n):
    """Return the number of paths from one corner of an
    M by N grid to the opposite corner.

    >>> paths(2, 2)
    2
    >>> paths(5, 7)
    210
    >>> paths(117, 1)
    1
    >>> paths(1, 157)
    1
    """
    "*** YOUR CODE HERE ***"
    if m == 1 or n == 1:
        return 1
    return paths(m - 1, n) + paths(m, n - 1)

Use Ok to test your code:

python3 ok -q paths

Q8: Increasing Subsequences

In Lab 4, we examined the Subsequences problem. A subsequence of a sequence S is a sequence of elements from S, in the same order they appear in S, but possibly with elements missing. For example, the lists [], [1, 3], [2], and [1, 3, 2] are subsequences of [1, 3, 2]. Again, we want to write a function that takes a list and returns a list of lists, where each individual list is a subsequence of the original input.

This time we have another condition: we only want the subsequences for which consecutive elements are nondecreasing. For example, [1, 3, 2] is a subsequence of [1, 3, 2, 4], but since 2 < 3, this subsequence would not be included in our result.

Fill in the blanks to complete the implementation of the inc_subseqs function. You may assume that the input list contains no negative elements.

You may use the provided helper function insert_into_all, which takes in an item and a list of lists and inserts the item to the front of each list.

def insert_into_all(item, lsts):
    """Assuming that lsts is a list of lists, return a new list consisting of
    all the lists in lsts, but with item added to the front of each.

    >>> lsts = [[], [1, 2], [3]]
    >>> insert_into_all(0, lsts)
    [[0], [0, 1, 2], [0, 3]]
    """
    return [[item] + lst for lst in lsts]

def inc_subseqs(s):
    """Assuming that S is a list, return a nested list of all subsequences
    of S (a list of lists) for which the elements of the subsequence
    are strictly nondecreasing. The subsequences can appear in any order.

    >>> seqs = inc_subseqs([1, 3, 2])
    >>> sorted(seqs)
    [[], [1], [1, 2], [1, 3], [2], [3]]
    >>> inc_subseqs([])
    [[]]
    """
    def subseq_helper(s, prev):
        if not s:
            return ____________________
            return [[]]
        elif s[0] < prev:
            return ____________________
            return subseq_helper(s[1:], prev)
        else:
            with_first = ______________________
            with_first = subseq_helper(s[1:], s[0])
            without_first = ______________________
            without_first = subseq_helper(s[1:], prev)
            return insert_into_all(________, ______________) + ________________
            return insert_into_all(s[0], with_first) + without_first
    return subseq_helper(____, ____)
    return subseq_helper(s, 0)

Use Ok to test your code:

python3 ok -q inc_subseqs

Sequences and Mutability

Q9: Dict to List

Fill in the blanks in the code to complete the implementation of the dict_to_lst function, which takes in a dictionary d and returns a list. The resulting list should contain all the (key, value) pairs in the input dictionary as two-element tuples, where the pairs with smaller values come first.

Note: The .items() method returns a collection of (key, value) pairs for a dictionary:

>>> for pair in {1: 2, 3: 4, 5: 6}.items():
...     print(pair)
(1, 2)
(3, 4)
(5, 6)

def dict_to_lst(d):
    """Returns a list containing all the (key, value) pairs in d as two-element
    tuples ordered by increasing value.

    >>> nums = {1: 5, 2: 3, 3: 4}
    >>> dict_to_lst(nums)
    [(2, 3), (3, 4), (1, 5)]
    >>> words = {'first': 'yes', 'second': 'no', 'third': 'perhaps'}
    >>> dict_to_lst(words)
    [('second', 'no'), ('third', 'perhaps'), ('first', 'yes')]
    """
    result = []
    for _ in range(len(d)):
        pair = min(d.items(), key=______________________)
        pair = min(d.items(), key=lambda item: item[1])
        d.pop(_________)
        d.pop(pair[0])
        _______________________
        result.append(pair)
    return result

# Alternate solution
# This solution is the ideal way to solve this problem, but we haven't learned
# how to use the sorted function so don't worry if you don't understand it.
def dict_to_list2(d):
    return sorted(d.items(), key=lambda pair: pair[1])

Use Ok to test your code:

python3 ok -q dict_to_lst

Q10: Filter

Write a function filter that takes in a list lst and predicate function pred and mutates lst so that it only contains elements satisfying pred.

Hint: Avoid mutating the list as you are iterating through it as this may cause issues with iterating through all the elements.

def filter(pred, lst):
    """Filters lst with pred using mutation.
    >>> original_list = [5, -1, 2, 0]
    >>> filter(lambda x: x % 2 == 0, original_list)
    >>> original_list
    [2, 0]
    """
    "*** YOUR CODE HERE ***"
    for e in lst[:]:
        if not pred(e):
            lst.remove(e)

# Alternate solution
def filter2(pred, lst):
    elems_to_remove = [e for e in lst if not pred(e)]
    for e in elems_to_remove:
        lst.remove(e)

Use Ok to test your code:

python3 ok -q filter

Q11: Replace All

Given a dictionary d, replace all occurrences of x as a value (not a key) with y.

Hint: You can iterate through the keys of a dictionary using a for statement:

>>> for k in {1: 2, 3: 4, 5: 6}:
...     print(k)
1
3
5

def replace_all(d, x, y):
    """Replace all occurrences of x as a value (not a key) in d with y.
    >>> d = {3: '3', 'foo': 2, 'bar': 3, 'garply': 3, 'xyzzy': 99}
    >>> replace_all(d, 3, 'poof')
    >>> d == {3: '3', 'foo': 2, 'bar': 'poof', 'garply': 'poof', 'xyzzy': 99}
    True
    """
    "*** YOUR CODE HERE ***"
    for key in d:
        if d[key] == x:
            d[key] = y

Use Ok to test your code:

python3 ok -q replace_all

More Tree Practice

Q12: Pruning Leaves

Define a function prune_leaves that given a tree t and a tuple of values vals, it produces a version of t with all its leaves that are in vals removed. Do not attempt to try to remove non-leaf nodes and do not remove leaves that do not match any of the items in vals. Return None if pruning the tree results in there being no nodes left in the tree.

def prune_leaves(t, vals):
    """Return a modified copy of t with all leaves that have a label
    that appears in vals removed.  Return None if the entire tree is
    pruned away.

    >>> t = tree(2)
    >>> print(prune_leaves(t, (1, 2)))
    None
    >>> numbers = tree(1, [tree(2), tree(3, [tree(4), tree(5)]), tree(6, [tree(7)])])
    >>> print_tree(numbers)
    1
      2
      3
        4
        5
      6
        7
    >>> print_tree(prune_leaves(numbers, (3, 4, 6, 7)))
    1
      2
      3
        5
      6
    """
    "*** YOUR CODE HERE ***"
    if is_leaf(t) and (label(t) in vals):
      return None
    new_branches = []
    for b in branches(t):
      new_branch = prune_leaves(b, vals)
      if new_branch:
        new_branches += [new_branch]
    return tree(label(t), new_branches)

Use Ok to test your code:

python3 ok -q prune_leaves

Q13: Add trees

Define the function add_trees, which takes in two trees and returns a new tree where each corresponding node from the first tree is added with the node from the second tree. If a node at any particular position is present in one tree but not the other, it should be present in the new tree as well.

Hint: You may want to use the built-in zip function to iterate over multiple sequences at once.

Note: If you feel that this one's a lot harder than the previous tree problems, that's totally fine! This is a pretty difficult problem, but you can do it! Talk about it with other students, and come back to it if you need to.

def add_trees(t1, t2):
    """
    >>> numbers = tree(1,
    ...                [tree(2,
    ...                      [tree(3),
    ...                       tree(4)]),
    ...                 tree(5,
    ...                      [tree(6,
    ...                            [tree(7)]),
    ...                       tree(8)])])
    >>> print_tree(add_trees(numbers, numbers))
    2
      4
        6
        8
      10
        12
          14
        16
    >>> print_tree(add_trees(tree(2), tree(3, [tree(4), tree(5)])))
    5
      4
      5
    >>> print_tree(add_trees(tree(2, [tree(3)]), tree(2, [tree(3), tree(4)])))
    4
      6
      4
    >>> print_tree(add_trees(tree(2, [tree(3, [tree(4), tree(5)])]), \
    tree(2, [tree(3, [tree(4)]), tree(5)])))
    4
      6
        8
        5
      5
    """
    "*** YOUR CODE HERE ***"
    if not t1:
        return t2
    if not t2:
        return t1
    new_label = label(t1) + label(t2)
    t1_children, t2_children = branches(t1), branches(t2)
    length_t1, length_t2 = len(t1_children), len(t2_children)
    if length_t1 < length_t2:
        t1_children += [None for _ in range(length_t1, length_t2)]
    elif len(t1_children) > len(t2_children):
        t2_children += [None for _ in range(length_t2, length_t1)]
    return tree(new_label, [add_trees(child1, child2) for child1, child2 in zip(t1_children, t2_children)])

Use Ok to test your code:

python3 ok -q add_trees

Orders of Growth

Q14: Boom

What is the order of growth in time for the following function boom? Use big-θ notation.

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

Q15: Zap (Orders of Growth)

What is the order of growth in time for the following function zap? Use big-θ notation.

def zap(n):
    i, count = 1, 0
    while i <= n:
        while i <= 5 * n:
            count += i
            print(i / 6)
            i *= 3
    return count