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))