Your name __________________________

Harvey Mudd College

CS 60 Practice Midterm Fall 1999

The exam is planned for 1 hour, 15 mins., during class. You may take up to 15 minutes longer if the room is not being used for something else.

Please provide answers to the problem groups directly on these pages. It is suggested that you look over the exam first to get an idea of how to apportion your time. Work so as to maximize total points; do not get stuck on one problem at the expense of others.

During the exam, you may refer to your own reference sheet, but you may not consult with others or use other materials.

When code is requested, exhibiting the correct idea is more important than syntactic precision.

The answers to these problems need not be exceptionally long. Please think through your solution before you plunge into a long exposition that might not address the main point of the question.

1. [15 points]

The Smithsonian wishes to use object-oriented programming techniques to organize information about its large collection of vehicles (automobiles, bicycles, motorboats, sailboats, submarines, airplanes, hover craft, balloons, horse-drawn carts, etc.). It wants to structure the collection using classes. In addition to having the above types of vehicles as classes, it might have the following classes: vehicle, motor_powered_vehicle, nature_powered_vehicle, personally_powered_vehicle, animal_powered_vehicle, land_vehicle, air_vehicle, water_vehicle, amphibious_vehicle, sumbmarine_vehicle, etc.

a. Show, using a diagram, how inheritance could be used to organize these classes.

b. Where would you include in the class definitions a data member representing "speed" , giving the nominal speed for that class of vehicle? (Note that for some types of vehicles, there might be more than one speed, e.g. an amphibious vehicle might have a different land speed and water speed.)

2. [15 points]

Use McCarthy's transformation to create a recursive (e.g. rex) program from the following flowchart.

3. [10 points]

The concept of an "and-or tree" is used in artificial intelligence problem solving. For our purpose, assume the following inductive definition of and-or tree:

• 0 and 1 are both and-or trees
• A tree having either "*" or "+" as a root and having and-or trees as immediate sub-trees is also an and-or tree.

The above rules describe the only ways to get an and-or tree.

For example, using a typical tree-as-list representation, the following are each and-or trees:

• 0
• 1
• ["+", 0, 1, 1, 0]
• ["*", 1, ["+", 0, 1, 1, 0], ["+", 0, 1], 0]

Moreover, an and-or tree is called solvable according to the following inductive rules:

• 1 is solvable
• A tree with "*" as the root is solvable if, and only if, each immediate sub-tree is solvable.
• A tree with "+" as the root is solvable if, and only if, at least one of its immediate sub-trees is solvable.

The above rules describe the only ways in which a tree is solvable.

For example, ["+", 0, 1, 1, 0] is solvable, but ["*", 1, ["+", 0, 1, 1, 0], ["+", 0, 1], 0] is not.

Give a set of rex rules for computing a function solvable, which tells whether its and-or tree argument is solvable. You may assume the tree is well-formed; you do not have to perform error-checking on the argument.

4. [15 points]

State as clearly as possible, and in your own words, the differences between the Polylist (or rex) functions cons, list (of 2 arguments only), and append. Give examples to help clarify.

5. [10 points]

A tree can be enlarged from the leaves downward by viewing the tree as a list and applying the map function to that list along with an appropriate function argument. For example, if the tree were [1, 2, 3], we could replicate its leaves side-by-side to get a new tree [[1, 1], [2, 2], [3, 3]].

a. Write a function which could be given as the first argument of map to achieve the transformation from [1, 2, 3] to [[1, 1], [2, 2], [3, 3]].

b. Using recursion, in conjunction with map, present rex rules for a single function which can replicate the leaves of an arbitrary tree. For example, replicating leaves in

[[1, 2], 3, [[4, 5], 6]]

should yield

[[[1, 1], [2, 2]], [3, 3], [[[4, 4], [5, 5]], [6, 6]]].

6. [15 points]

Consider the set S of functions with domain and range being subsets of the natural numbers. For example, the factorial function fac is such a function.

Construct rex definitions for a Curried higher-order function inverse which will produce the inverse of an arbitrary function in S. The inverse of a function is here defined to be another function which, given a result of the original function, produces the smallest argument of the original function which would have yielded that result. For example, since we have

fac(0) = 1, fac(1) = 1, fac(2) = 2, fac(3) = 6, fac(4) = 24, fac(5) = 120, ...

we would have

inverse(fac)(1) = 0, inverse(fac)(2) = 2, inverse(fac)(6) = 3, inverse(fac)(24) = 4,

inverse(fac)(120) = 5, ...

Note that when there might have been more than one possible answer, as is the case with inverse(fac)(1), we used the convention that the smallest such answer is returned by inverse. So inverse(fac)(1) is 0 rather than 1. Also, when there is no possible answer, inverse will diverge (give no answer). So inverse(fac)(3), for example, will diverge.

The inner workings of inverse will have to try evaluating the argument function for successive values 0, 1, 2, ... until one is found which works. So this would be the rex equivalent of a while loop. Also be reminded that your definition must work for an arbitrary function argument, not just fac.

7. [20 points]

Ring structures of the type below are sometimes used as a basis for text editors. Construct a reasonably efficient Java function which will accomplish linking of two structures, in the manner shown below:

before linking:

after linking:

Give a brief definition for the cell class that you use, so that the code makes sense.

Make sure your code works for the example given.