Due by 11:59pm on Wednesday, 4/3
Submission. See the online submission instructions. We have provided a starter file for the questions below.
Readings. Section 3.3 of the online lecture notes.
In lecture, we considered sets implemented as sorted recursive lists:
def empty(s):
return len(s) == 0
def set_contains2(s, v):
"""Return true if set s contains value v as an element.
>>> set_contains2(s, 2)
True
>>> set_contains2(s, 5)
False
"""
if empty(s) or s.first > v:
return False
if s.first == v:
return True
return set_contains2(s.rest, v)
def intersect_set2(set1, set2):
"""Return a set containing all elements common to set1 and set2.
>>> t = Rlist(2, Rlist(3, Rlist(4)))
>>> intersect_set2(s, t)
Rlist(2, Rlist(3))
"""
if empty(set1) or empty(set2):
return Rlist.empty
e1, e2 = set1.first, set2.first
if e1 == e2:
return Rlist(e1, intersect_set2(set1.rest, set2.rest))
if e1 < e2:
return intersect_set2(set1.rest, set2)
if e2 < e1:
return intersect_set2(set1, set2.rest)
Q1. Implement adjoin_set2, which adjoins an element to a set using the sorted recursive list implementation from lecture:
def adjoin_set2(s, v):
"""Return a set containing all elements of s and element v.
>>> adjoin_set2(s, 2.5)
Rlist(1, Rlist(2, Rlist(2.5, Rlist(3))))
"""
"*** YOUR CODE HERE ***"
Q2. Implement union_set2, which computes the union of two sets represented as sorted recursive lists:
def union_set2(set1, set2):
"""Return a set containing all elements either in set1 or set2.
>>> t = Rlist(1, Rlist(3, Rlist(5)))
>>> union_set2(s, t)
Rlist(1, Rlist(2, Rlist(3, Rlist(5))))
"""
"*** YOUR CODE HERE ***"
In lecture, we also considered sets represented as trees:
def set_contains3(s, v):
"""Return true if set s contains value v as an element.
>>> t = Tree(2, Tree(1), Tree(3))
>>> set_contains3(t, 3)
True
>>> set_contains3(t, 0)
False
>>> set_contains3(big_tree(20, 60), 34)
True
"""
if s is None:
return False
if s.entry == v:
return True
if s.entry < v:
return set_contains3(s.right, v)
if s.entry > v:
return set_contains3(s.left, v)
def adjoin_set3(s, v):
"""Return a set containing all elements of s and element v.
>>> b = big_tree(0, 9)
>>> b
Tree(4, Tree(1), Tree(7, None, Tree(9)))
>>> adjoin_set3(b, 5)
Tree(4, Tree(1), Tree(7, Tree(5), Tree(9)))
"""
if s is None:
return Tree(v)
if s.entry == v:
return s
if s.entry < v:
return Tree(s.entry, s.left, adjoin_set3(s.right, v))
if s.entry > v:
return Tree(s.entry, adjoin_set3(s.left, v), s.right)
Q3. Implement depth, which returns the depth of a value in a set represented as a tree:
def depth(s, v):
"""Return the depth of the value v in tree set s.
The depth of a value is the number of branches followed to reach the value.
The depth of the root of a tree is always 0.
>>> b = big_tree(0, 9)
>>> depth(b, 4)
0
>>> depth(b, 7)
1
>>> depth(b, 9)
2
"""
"*** YOUR CODE HERE ***"
Q4. Implement tree_to_ordered_sequence, which coerces a set represented as a tree into a set represented as an ordered sequence. (Extra for experts) Implement this function so that it executes in Theta(n) time, where n is the number of elements in the tree:
def tree_to_ordered_sequence(s):
"""Return an ordered sequence containing the elements of tree set s.
>>> b = big_tree(0, 9)
>>> tree_to_ordered_sequence(b)
Rlist(1, Rlist(4, Rlist(7, Rlist(9))))
"""
"*** YOUR CODE HERE ***"
Q5. In order to complete the coercion from an ordered sequence set to a tree set, implement partial_tree. (Extra for experts) Implement the function to run in Theta(n) time.
Hint: This function requires two recursive calls. The first call builds a left branch out of the first left_size elements of s; Then, the next elemnt is used as the entry of the returned tree. Finally, the second recursive call builds the right branch out of the next right_size elements. In total, (left_size + 1 + right_size) = n, where 1 is for the entry:
def partial_tree(s, n):
"""Return a balanced tree of the first n elements of Rlist s, along with
the rest of s. A tree is balanced if the length of the path to any two
leaves are at most one apart.
>>> s = Rlist(1, Rlist(2, Rlist(3, Rlist(4, Rlist(5)))))
>>> partial_tree(s, 3)
(Tree(2, Tree(1), Tree(3)), Rlist(4, Rlist(5)))
"""
if n == 0:
return None, s
left_size = (n-1)//2
right_size = n - left_size - 1
"*** YOUR CODE HERE ***"
def ordered_sequence_to_tree(s):
"""Return a balanced tree containing the elements of ordered Rlist s.
A tree is balanced if the lengths of the paths from the root to any two
leaves are at most one apart.
Note: this implementation is complete, but the definition of partial_tree
above is not complete.
>>> ordered_sequence_to_tree(Rlist(1, Rlist(2, Rlist(3))))
Tree(2, Tree(1), Tree(3))
>>> b = big_tree(0, 20)
>>> elements = tree_to_ordered_sequence(b)
>>> elements
Rlist(1, Rlist(4, Rlist(7, Rlist(10, Rlist(13, Rlist(16, Rlist(19)))))))
>>> ordered_sequence_to_tree(elements)
Tree(10, Tree(4, Tree(1), Tree(7)), Tree(16, Tree(13), Tree(19)))
"""
return partial_tree(s, len(s))[0]
If tree_to_ordered_sequence and ordered_sequence_to_tree run in linear time, then so will intersect_set3 and union_set3 below:
def intersect_set3(set1, set2):
"""Return a set containing all elements common to set1 and set2.
>>> s, t = big_tree(0, 12), big_tree(6, 18)
>>> intersect_set3(s, t)
Tree(8, Tree(6), Tree(10, None, Tree(12)))
"""
s1, s2 = map(tree_to_ordered_sequence, (set1, set2))
return ordered_sequence_to_tree(intersect_set2(s1, s2))
def union_set3(set1, set2):
"""Return a set containing all elements either in set1 or set2.
>>> s, t = big_tree(6, 12), big_tree(10, 16)
>>> union_set3(s, t)
Tree(10, Tree(6, None, Tree(9)), Tree(13, Tree(11), Tree(15)))
"""
s1, s2 = map(tree_to_ordered_sequence, (set1, set2))
return ordered_sequence_to_tree(union_set2(s1, s2))
This appendix implements the Rlist and Tree classes from lecture:
class Rlist(object):
"""A recursive list consisting of a first element and the rest."""
class EmptyList(object):
def __len__(self):
return 0
empty = EmptyList()
def __init__(self, first, rest=empty):
self.first = first
self.rest = rest
def __repr__(self):
args = repr(self.first)
if self.rest is not Rlist.empty:
args += ', {0}'.format(repr(self.rest))
return 'Rlist({0})'.format(args)
def __len__(self):
return 1 + len(self.rest)
def __getitem__(self, i):
if i == 0:
return self.first
return self.rest[i-1]
def extend_rlist(s1, s2):
"""Return a list containing the elements of s1 followed by those of s2."""
if s1 is Rlist.empty:
return s2
return Rlist(s1.first, extend_rlist(s1.rest, s2))
def map_rlist(s, fn):
"""Return a list resulting from mapping fn over the elements of s."""
if s is Rlist.empty:
return s
return Rlist(fn(s.first), map_rlist(s.rest, fn))
def filter_rlist(s, fn):
"""Filter the elemenst of s by predicate fn."""
if s is Rlist.empty:
return s
rest = filter_rlist(s.rest, fn)
if fn(s.first):
return Rlist(s.first, rest)
return rest
s = Rlist(1, Rlist(2, Rlist(3))) # A set is an Rlist with no duplicates
class Tree(object):
"""A tree with internal values."""
def __init__(self, entry, left=None, right=None):
self.entry = entry
self.left = left
self.right = right
def __repr__(self):
args = repr(self.entry)
if self.left or self.right:
args += ', {0}, {1}'.format(repr(self.left), repr(self.right))
return 'Tree({0})'.format(args)
def big_tree(left, right):
"""Return a tree of elements between left and right.
>>> big_tree(0, 12)
Tree(6, Tree(2, Tree(0), Tree(4)), Tree(10, Tree(8), Tree(12)))
"""
if left > right:
return None
split = left + (right - left)//2
return Tree(split, big_tree(left, split-2), big_tree(split+2, right))