Lab 05: Orders of Growth and Hierarchical Data Structures

Table of Contents

Deadline

By the end of this lab, you should have submitted the lab05 assignment using the command submit lab05.

This lab is due by 11:59pm on 7/10/2014.

Here is a lab05.py starter file for this lab.

Trees

Trees are a way we have of representing a hierarchy of information. A file directory is a good example of something with a tree structure. You have a root folder that contains several other folders — home, bin, user, etc. — and within each of these there exists a similar hierarchy.

The name "tree" comes from the branching structure, like real trees in nature except that they're drawn with the root at the top and the leaves at the bottom.

Terminology:

Implementation

For this lab, we will be using trees according to the following specification unless otherwise stated.

A tree consists of a datum and a list of children. Each of these children is itself a tree. A leaf is represented as a tree whose list of children is an empty list.

Our implementation of trees can be found in lab05.py, though since it is an ADT, the implementation is not important. The interface for our trees consists of the following functions:

# Constructor
tree(datum, children=[]) 

# Selectors
datum(tree)            
children(tree)          

Therefore 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 3 from this tree, we would do this:

datum(children(t)[1])

Question 1

Define the function size_of_tree, which takes in a tree as an argument and returns the number of entries in the tree.

def size_of_tree(t):
    """Return the number of entries in the tree.

    >>> print_tree(t)
    1
      2
      3
        4
        5
      6
        7
    >>> size_of_tree(t)
    7
    """
    "*** YOUR CODE HERE ***"
def size_of_tree(t):
    return 1 + sum([size_of_tree(t) for t in children(t)])

OR

def size_of_tree(t):
    children_sum = 0
    for child in children(t):
        children_sum += size_of_tree(child)
    return 1 + children_sum

Question 2

Define the function flatten, which takes in a tree as an argument and returns a list of all the entries in the tree in the order that print_tree would print them. This ordering of the nodes in a tree is called a preorder traversal (you will learn about more orders of traversing a tree in CS 61B).

def flatten(t):
    """Return a list of the entries in this tree in the order that they 
    would be visited by a preorder traversal (see problem description).

    >>> flatten(t)
    [1, 2, 3, 4, 5, 6, 7]
    >>> flatten(tree(2, [tree(4, [tree(6)])]))
    [2, 4, 6]
    """
    "*** YOUR CODE HERE ***"
from functools import reduce
from operator import add

def flatten(t):
    return reduce(add, [flatten(child) for child in children(t)], [datum(t)])

OR

def flatten(t):
    if children(t) == []:
        return [datum(t)]
    flattened_children = []
    for child in children(t):
        flattened_children += flatten(child)
    return [datum(t)] + flattened_children

Question 3

Define the function tree_map, which takes in a tree and a one-argument function as arguments and returns a new tree which is the result of mapping the function over the entries of the input tree.

def tree_map(fn, t):
    """Maps the function fn over the entries of tree and returns the 
    result in a new tree.

    >>> print_tree(tree_map(lambda x: 2**x, t))
    2
      4
      8
        16
        32
      64
        128
    """
    "*** YOUR CODE HERE ***"
def tree_map(fn, t):
    return tree(fn(datum(t)), [tree_map(fn, t) for t in children(t)])

OR

def tree_map(fn, t):
    if children(t) == []:
        return tree(fn(datum(t)), [])
    mapped_children = []
    for child in children(t):
        mapped_children += [ tree_map(fn, child) ]
    return tree(fn(datum(t)), mapped_children)

Midterm 1 Review Questions

The rest of the questions on this lab will not be turned in for Lab

  1. They are meant for you to get more practice.

Here is a review1.py starter file for this section.

Environment Diagrams

Draw the environment diagrams for the following questions.

Question 4

def funny(joke):
    hoax = joke + 1
    return funny(hoax)

def sad(joke):
    hoax = joke - 1
    return hoax + hoax

funny, sad = sad, funny
result = funny(sad(1))

Question 5

def fun(fun):
    def time(time):
        return fun(x)
    x = 4
    return time

def boo(x):
    return x**2
x = 5
result = fun(boo)(10)

Question 6

def easy(x):
    def peasy(y):
        def ironic(name):
            return name(x, y)
        return y
    return peasy

result = easy(4)(easy)(2)

Data Abstraction

Question 7

Suppose that your friend wrote the following function prod_rats that takes a list of rational numbers using our ADT and returns their product. Correct their code so that they do not have any data abstraction violations.

def prod_rats(rats):
    """Returns a rational number that is the product of the rational
    numbers in rats.
    >>> x = prod_rats([make_rat(2, 4), make_rat(5, 9), make_rat(6, 4)])
    >>> num(x)
    5
    >>> den(x)
    12
    """
    total, i = [1, 1], 0
    while i < len(rats):
        total = [total[0]*rats[i][0], total[1]*rats[i][1]]
        i += 1
    g = gcd(total[0], total[1])
    return [total[0] // g, total[1] // g]
def prod_rats(rats):
    total, i = make_rat(1, 1), 0
    while i < len(rats):
        total = mul_rat(total, rats[i])
        i += 1
    return total

Linked Lists

Question 8

Write a function that returns a new linked list that is the same as lst with elem added at the end.

def insert_at_end(lst, elem):
    """Return a linked list that is the same as lst with elem added
    at the end.

    >>> lst1 = link(1, link(2, empty))
    >>> print_linked_list(lst1)
    < 1 2 >
    >>> lst2 = insert_at_end(lst1, 3)
    >>> print_linked_list(lst2)
    < 1 2 3 >
    """
    "*** YOUR CODE HERE ***""
def insert_at_end(lst, elem):
    if lst == empty:
        return link(elem, empty)
    else:
        return link(first(lst), insert_at_end(rest(lst), elem))

Question 9

Write a function that uses the previous insert_at_end function and returns a new list that contains the elements of lst in reverse order.

def reverse(lst):
    """Returns a new list that contains the elements of lst in reverse order.

    >>> lst = link(1, link(2, link(3, empty)))
    >>> print_linked_list(lst)
    < 1 2 3 >
    >>> reversed_lst = reverse(lst)
    >>> print_linked_list(reversed_lst)
    < 3 2 1 >
    """
    "*** YOUR CODE HERE ***"
def reverse(lst):
    if lst == empty:
        return empty
    else:
        return insert_at_end(reverse(rest(lst)), first(lst))

Functions

Question 10

Determine the result of the following expression.

from operator import add, sub, mul, truediv

truediv(mul(add(5, 3), sub(4, 2)), 4)

Question 11

What would Python print?

from operator import mul

def hi():
    print(“yummy”)
    return mul

def welcome():
    print("chicken")
    return max

def to():
    print("dinner")
    return 5

def cs61a():
    print("winner")
    return 10

hi()(welcome()(to(), cs61a()), welcome()(cs61a(), to()))

Question 12

Fill in the blanks so that the doctests pass!

def catchphrase(say, person):
    """
    >>> say = lambda a: 'Darknesss' if a == 'Nocturne' else 'Mundo'
    >>> phrase = catchphrase(say, None)
    Welcome to Summoner's Rift!
    >>> phrase 
    False
    >>> catchphrase(say, 'Mundo')
    'Mundo'
    >>> catchphrase(say, 'Nocturne')
    'report feeder'
    """
    if ______:
        print("Welcome to Summoner's Rift!")
        return ______
    if say(person) == 'Darknesss':
        return 'report feeder'
    else:
        _____
def catchphrase(say, person):
    if person == None:
        print("Welcome to Summoner's Rift!")
        return False
    if say(person) == 'Darknesss':
        return 'report feeder'
    else:
        return person