This review sheet is intended to help you study for the second midterm exam. It is not intended to be an exhaustive list of everything we've covered, but it should help you identify the "big ideas". Note that the midterm will cover all topics we've seen so far, including those that we covered before midterm 1. However, emphasis will be placed on topics since the last exam (i.e., at least 75% of the points will be for topics since the last exam).
You should also review your lecture notes and the solutions to your homework problems. The lecture "quizzes" are especially useful in helping you study for the exam.
You may bring to the exam a 8.5 by 11 sheet with your own writing (only) on both sides.
You've been hired by Millisoft, a major software company. Your first job is to write a class called BasicDictionary that supports the dictionary abstract data type operations of insert and find. The insert method takes a reference to an object and inserts it into the dictionary. The dictionary will be implemented as a binary search tree (but not a fancy one like an AVL tree or a B-Tree). More on that in a moment!
The objects that are being inserted and found might be anything, but it is assumed that there is some ordering of the objects. For example, if the objects are numbers, the ordering could be numerical order. If the objects are strings, the ordering might be alphabetical ordering. If the objects are canned meat products, the ordering might be the order in which the products were made. In general they will be objects made from some class that is expected to have a class method called lessThan that is expected to take as input two of these objects, o1 and o2 and return a boolean: It will return True if o1 is less than o2 in this particular ordering and it will be False otherwise. For example, you could invoke this function by calling o1.lessThan(o1, o2) to compare objects o1 and o2. As the developer of the BasicDictionary class, you don't need to worry about how the lessThan method works, you can just assume that you are dealing with a class that has this method available.
Your job is to give an implementation of the BasicDictionary class using a binary search tree implementation. Below is the starter code with comments. Just implement the insert method, not the find method.
class TreeNode(object):
def __init__(self, data):
self.data = data
self.lessChild = None
self.greaterChild = Noneclass BasicDictionary(object):
def __init__(self):
self.root = None # root is a reference to the root of the tree
def insert(self, data):
# Fill in code here.
class Person(object):
def __init__(self, name):
self.name = name
def isAsleep( self, hr ):
return 22 < hr or 7 > hr
def __repr__(self):
return self.name
def status( self, hr ):
if self.isAsleep( hr ):
print "Now offline: " + self
else:
print "Now online: " + this
class Student(Person):
def __init__(self, name, units):
super(Student, self).__init__(name)
self.units = units
def isAsleep( self, hr ):
return 2 < hr and 8 > hr
def __repr__(self):
result = super(Student, self).__repr__()
return result + " units: " + str(self.units)