This review sheet is intended to help you study for the 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". 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.
Please remember that you may bring to the exam a 8.5 by 11 sheet with your own writing on both sides.
Scheme> (foldr (lambda (X, Y) (+ X Y)) 0 '(1, 2, 3, 4))You should assume that foldr "associates" (orders operations) like this: 1 + 2 + 3 + 4 = 1 + (2 + (3 + (4 + 0))). (Notice that the 0 at the end is the unit for addition.) Write the foldr function from scratch. That is, your implementation my use Scheme's list notation and recursion, but no built-in functions. Notice that foldr should not be written exclusively to handle addition! It's first argument can be any function of two variables, its second argument is the unit for that function, and its third argument is a list of elements of the type operated on by the given function.
10
You have been hired by Napquest, a company specializing in finding shortest paths between given cities. (It's called Napquest, because their algorithms tend to be inefficient, causing the users to nap while they wait for the answer!)
A map is a list of "triplets", where each triplet is a list of the form [City1, City2, Distance]. City1 and City2 are just names of cities (e.g. they might be numbers or strings) and Distance is a positive real number indicating the length of the one-way road from City1 to City2. For example, here is a valid map: [ ["Claremont", "Spamville", 1], ["Spamville", "Claremont", 2], ["Spamville", "Foobarsburg", 2], ["Foobarsburg", "Claremont", 4] ]. Notice that the map may contain cycles and that there may be funny things like a one-way road from Claremont to Spamville which is shorter than the one-way road from Spamville to Claremont.
Your job is write a program called tour which
takes as
input two things: The name of the start city, and an entire map. The
function returns a boolean that indicates whether there is a path
starting in the start city that tours all of the cities (it does not
need to return to the start city).
The program need not be fast, but it must compute the
right answer. For full credit, keep your code very short. However you may find it easier to write a helper function.
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 public static method called lessThan that is expected to take as input two of these objects, o1 and o2 and return a boolean: It will true if o1 is less than o2 in this particular ordering and it will be false otherwise. 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.
Finally, BasicDictionary uses parameterized types (generics). This would allow us to use this class from a different function by doing something like BasicDictionary<String> myD = new BasicDictionary<String>();.
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 BasicDictionary<DataType>
{
class TreeNode
{
private <DataType> data;
private TreeNode lessChild;
private TreeNode greaterChild;
TreeNode(<DataType> data)
{
this.data = data;
this.lessChild = null;
this.greaterChild = null;
}
}
protected TreeNode root; // Reference to the root of the tree
BasicDictionary()
{
this. root = null;
}
public void insert(<DataType> data)
{
// FILL IN THIS CODE
}
}