Due by 4pm on Wednesday, 14 March
You can grab a template for this homework either by downloading the file from the calendar or by running the following command in terminal on one of the school computers (the dot is significant: it denotes the current directory)
cp ~cs61a/lib/hw/hw8.py .
Readings. Chapter 3.3
Q1. Write a version of tree_find from lecture (for finding keys among the labels of a binary search tree) that is purely iterative and does not use recursion.
Q2. Define a function depth that, given a Tree, T, and a value, x, finds the depth at which x appears as a label in the tree. Depth here refers to distance from the root, T. The node T itself is at depth 0; its children are at depth 1, etc. Assume that x appears at most once in the tree. Return None if it does not appear.
Q3. Generalize the binary search trees from lecture to search trees with more than two children. We can define a general search tree as one whose labels are lists of keys such that
- A node whose label is None represents an empty collection.
- Otherwise, there is at least one key in a node label and the keys are sorted in ascending order.
- A non-empty node with N keys has N+1 children, which are also general search trees.
- If x is key #k in a node's label, then all keys in child #k are less than x and all those in child #k+1 are greater than x.
Fill in the definition of gen_tree_find in the skeleton to search for a key in such a general search tree.
Q4. Write a higher-order function that generalizes memoization:
def memoize(func):
"""Returns a function that takes the same arguments as 'func'
and returns the same value, but with memoization. That is, if
f is the function returned by memoize(func), then f(v) returns
func(v), but if f is called twice with the same arguments, v, it
does not call func(v), but returns the previously returned value.
We assume that 'func' is a pure function whose value depends only
on the values of its arguments, and whose side-effects are irrelevant,
and that the values of its argument, v, are of a type
suitable for use as keys
in a Python dictionary."""
So, for example, if we define:
def fib(x):
print(x)
if x <= 1:
return 1
else:
return fib(x-2) + fib(x-1)
fib = memoize(fib)
and then call fib(6), we'd get the expected return value (13), but the printed values would be 0, 1, 2, 3, 4, 5, 6, instead of the sequence we would expect from the unmemoized fib, which is 0, 1, 2, 0, 1, 3, 1, 2, 0, 1, etc.
Your memoize function should work with functions that take any number of parameters. Reminder: In Python, the syntax:
def f(*a): ...
allows f to take any number of parameters (0 or more), setting a to a tuple containing them. Likewise, if g is a function taking two parameters, then:
>>> g(1, 2) 42 >>> v = (1, 2) >>> g(*v) 42
Q5. Modify your solution to Q4 so that if the calculation of func(v) for some value of v causes a recursive call of func(v) (that is, a call with the same arguments, indicating an infinite loop), then the memoized function raises a RuntimeError exception. Call the new version checked_memoize.
Q6. Consider the following definition of adjoin_set, adapted to the binary search trees in this problem set, and adjoin_all:
empty_set = Tree(None)
def adjoin_set(S, v):
"""Assuming S is a binary search tree representing a set (no
duplicate values), the binary search tree representing the set
S U {v}."""
if S.label is None:
return Tree(v, None, None)
elif v < S.label:
return Tree(S.label, adjoin_set(S[0], v), S[1])
elif v == S.label:
return S
else:
return Tree(S.label, S[0], adjoin_set(S[1], v))
def adjoin_all(S, L):
"""The result of adding all the elements of L to set S, in order."""
for v in L:
S = adjoin_set(v)
return S
Define two functions: bad(N) and good(N) that each returns a sequence of N non-null integer values such that tree_find(adjoin_all(empty_set, bad(N)), x) takes as long as possible for any given value N and the worst x, and tree_find(adjoin_all(empty_set, good(N)), x) takes as little time as possible for any given value N and the worst x.
Q7. [Extra for experts] Write a function that returns the result of removing a value from a binary search tree, if it is present (maintaining the search-tree property, of course). Returns the original tree if the value is not present. The time spent should be proportional to the depth of the tree. Hint: This is easy if the node whose label matches the value being deleted contains at most one non-empty child. The tricky part is figuring out what to do when that node has two non-empty children.
Q8. [Extra for experts] Define a function preorder(T) on Trees that returns an iterator over the labels in T in preorder. That is, it lists a node's label first, then those of its children (recursively) in order. (For this problem, there are no empty trees; None is just a possible label value):
""" >>> T = Tree(1, Tree(2, Tree(3, 4, 5), 6), 7, 8) >>> list(preorder(T)) [1, 2, 3, 4, 5, 6, 7, 8] """