You may take the final exam either on
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 exam will be worth about 200 points, i.e., two normal hw assignments.
Please remember that you may bring two 8.5 by 11 sheets with writing on both sides to the exam.
These were practice problems for the midterm (but they don't hurt here, either). The "official" practice exam problems are at this link.
rex> reduce( (X, Y) => X+Y, 0, [1, 2, 3, 4]) 10You should assume that reduce "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 reduce function from scratch. That is, your implementation my use rex's list notation and recursion, but no built-in functions. Notice that reduce 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.
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 shortest which takes as input three things: The name of the start city, the name of the end city, and an entire map. The function returns a single positive real number, namely the length of the shortest path from the start city to the end city. If there is no path from the start city to the end city, the shortest path length should be Infinity (a value built-in to rex).
The program need not be fast, but it must compute the right answer. For full credit, keep your code very short. If your code is more than 8 lines long, it's too long!
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
}
}