Your name __________________________
Harvey Mudd College
CS 60 Practice Midterm Fall 2000
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). It wants to structure the collection using classes. In addition to having the above types of vehicles as classes, the museum is considering creating the following classes: vehicle, motor_powered_vehicle, nature_powered_vehicle, personally_powered_vehicle, animal_powered_vehicle, land_vehicle, air_vehicle, and water_vehicle.
a. Show, using a diagram, how inheritance could be used to organize these classes. Are there any problems that arise? If so, how might you get around them?
b. What would be an example of a method that you might want to include in the vehicle class, but not override in any derived classes? What would be an example of a method that you might want to include in the vehicle class, but that would be overridden by all of its derived classes?
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:
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:
Moreover, an and-or tree is called solvable according to the following inductive rules:
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.
a. What is the difference between these "and-or" trees and the expressions (using only the "*" and "+" operators) that you parsed in assignment 7? What property of logical expressions corresponds to the above notion of "solvable" ?
b. Give a set of rex rules that implements a function named solvable(T), 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. [10 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]
Given the following grammar that describes certain integers, digit-by-digit:
S -> { D } L
L -> E F | O T ( note that this is the letter O )
F -> 0 | 4 | 8 ( and this is the number 0 )
T -> 2 | 6
E -> F | T
O -> 1 | 3 | 5 | 7 | 9
( the letter O on both these lines: O for "Odd" )
D -> E | O
a. Which of the two expressions "1986" or "1988" is an expression that this grammar can generate? Write the derivation tree (parse tree) for that expression. How might you describe all (and only) the integers this grammar generates?
b. Write a grammar that generates any (and only) strings of a's
and b's such that there are an even number of a's and
at most 1 b.
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.