cs60 midterm fall 97

Your name __________________________

Harvey Mudd College

CS 60 Mid-Term Exam

Fall semester, 2001

Five Problems

90 Points

Closed book

Instructions

During the exam, the only item to which you may refer is your own reference sheet, one double-sided sheet of 8.5" x 11" paper.

The exam has a time limit of 50 minutes. Work so as to maximize total points; do not get stuck on one problem at the expense of others. It is suggested that you look over the exam first to get an idea of how to apportion your time.

Please provide answers to the problems directly on these pages.

For each problem, the action items are shown in boldface.

When code is requested, exhibiting the correct idea is more important than syntactic precision. However, keep your definitions clean and readable. Use the clearest program structure possible.

1. [15 points] (Answer)

Using the rex language, construct a function keep_indices that takes a single-argument predicate and a list as arguments and returns the indices of the elements that satisfy the predicate. The indices of list elements are defined to be numbered 0, 1, 2, 3, … .

Example:

keep_indices(odd, [1, 3, 2, 4, 3, 1, 6, 8]) == [0, 1, 4, 5]
  (indices of odd)              

                   0  1  2  3  4  5  6  7

Hint: Use one or more auxiliary functions. You are advised to use low-level functional programming, rather than trying to compose known high-level functions.

2. [40 points] (Answer)

On the Worldwide Web, web pages are identified by Uniform Resource Identifiers (URI’s, sometimes informally called URL’s), which are strings that identify resources. A given web page may link to other web pages by giving their URI’s. Suppose we abstract the links of web pages as a function:

links

such that, for any given URI U, the value links(U) is the list of URI’s of pages to which the page links.

Using the rex language, assume you have a function from links as described. Construct a function accesses such that accesses(U) is the list of URI’s accessible from U in one or more steps.

Example: Suppose that

links("a") == ["b", "d", "g"]

links("b") == ["d", "e", "f"]

links("c") == ["b", "f"]

links("d") == []

links("e") == ["a"]

links("f") == [ ]

links("g") == [ ]

Then it would be the case that

accesses("b") == ["a", "b", "d", "e", "f", "g"]

Hint: Use one or more auxiliary functions. Make sure that your function does not loop infinitely, even when, as in the example, one can follow links to end up at the starting page.

3. [10 points] (Answer)

The function defined below in the rex language provides one way of computing non-negative integer powers of a number. (This method is sometimes called the "Russian Peasant’s method and is regarded by some as being a computationally more efficient method than the obvious way.)

// power(M, N) is M to the N^th power

power(M, 0) => 1;

power(M, N) => odd(N)? M * power(M*M, N/2);

power(M, N) => power(M*M, N/2);

Indicate why this implementation not tail-recursive, then give an equivalent tail-recursive implementation for power.

Hint: Use an auxiliary function and an accumulator.

4. [10 points] (Answer)

Consider a Java interface Complex for complex numbers, with defined methods as given below:

interface Complex
{
double getX();
double getY();
double getR();
double getTheta();
}

The given methods (which are implicitly public by Java rules, because they are in an interface) allude to two possible representations of complex numbers; one by Cartesian coordinates (X, Y) and a second representation by polar coordinates (R, Theta). These representations satisfy the following relationships:

R == sqrt(X*X + Y*Y)

Theta == atan(Y/X)

X == R*cos(Theta)

Y == R*sin(Theta)

Construct two Java classes, each of which implements interface Complex:

Class Cartesian implements the interface by defining private variables X and Y.

Class Polar implements the interface by defining private variables R and Theta.

Each class should have one constructor, which accepts the pair of values used in its respective representation.

Assume that you have available the Java functions Math.sqrt, Math.atan, Math.cos, and Math.sin.

5. [15 points] (Answer)

Unlike functional programs, object-oriented programs, for better or worse, permit the modification of objects in place. For example, given a list of Integer, we might want to replace the values in the Integers with new ones. Unfortunately, this is not possible, since objects of class Integer are immutable. However, we can construct our own class MutableInteger that has a single int value, and define a setter and getter methods for this value.

Assuming that we have a list of MutableInteger objects, show how to use an Iterator to replace the value of each item in the list by its square. Note that we want to change only the contents of the items, not the structure of the list.

Recall that the interface Iterator has the following methods:

Object next();

boolean hasNext();

Assume that our list has the method

Iterator getIterator();

which returns an iterator capable of traversing the list.