Solutions to Review Questions for Prelim I

CS211 - Fall 2000

Please let me know via email (chew@cs.cornell.edu) if you find mistakes in the solutions. Past experience indicates that I may have made some.

Problem 1

The great conductor Seiji Ojava has set up a rather tangled Java program with the classes and interfaces shown in Figure 1.

A skeleton code for interface C is shown below:

interface C extends A, B { ... }

Answer the following questions about this program.

(2 points) Write down a skeleton code for class F.
class F extends D implements A {...}
(2 points) Write down a skeleton code for class E.
class E extends D implements A, B {...}
(2 points per statement) Which of the following statements is legal? Explain each answer briefly. No credit will be given unless your explanation makes sense. Each statement should be considered independently of the others.

A r = new A();
Illegal; A is an interface and cannot be instantiated.

A r = new F();
Legal; F implements A, so objects of type F can be assigned to variables of type A.

A r = (A)(new F());
Legal; F implements A, so a reference of type F can be cast to a reference of type A.

A r = new G();
Legal; G extends F which implements A, so G also implements A.

F r = new G();
Legal; class G is a subclss of F.

G r = new F();
Illegal; an F is not necessarily a G, so this is a compile-time error.

G r = (G)(new F());
Illegal; an F is not necessarily a G. For this example, the compiler is happy (since an F might be a G), but at runtime ClassCastException is generated.

B r = new I();
Legal; class I implements interface C so it also implements all superinterfaces of C, one of which is B.

Problem 2

Java Nagila is learning about complex numbers. She has written a class named Complex for representing complex numbers, shown on the next page. She forgot to include methods for updating the real and imaginary parts of complex numbers. Fortunately, she remembered that she could use inheritance to extend the behavior of classes, so she wrote a new class called BComplex, declared to be a subclass of Complex, that has methods for updating the real and imaginary parts of complex number. Finally, she wrote a client class that tests these classes out. These classes are shown on the next page. Unfortunately, when she went to compile and run this program, the Java compiler gave her many errors. Fortunately, you are her 211 consultant, so she immediately came to see you for help. Explain to Java Nagila the errors she made, specifying the line number of each line that needs to be fixed, explaining briefly what the error is, and showing her how to fix it. For example,

Line 6 Constructor must have same name as class name. 
       Java is case-sensitive. So change complex to Complex.

Be sure to read the comments to figure out what Java Nagila had intended to write.

1. //class for Complex numbers
2. class Complex {
3. 	private float x;
Instance variable should be declared protected so that subclasses can access it.
4. 	private float y;
Instance variable should be declared protected so that subclasses can access it.
5. 	//constructor for class Complex
6. 	public Complex complex(float r, float i) {
Constructors do not have a return type; replace with public Complex (float r, float i) {
7. 		//initialize instance variable x
8. 		float x = r;
This introduces a new local variable x; remove the "float".
9. 		//initialize instance variable y
10. 		float y = i;
This introduces a new local variable y; remove the "float".
11. 	}
12. 	//return real part of complex number
13. 	public int Re() {
Return type of method must be float.
14. 		return x;}
15. 	//return imaginary part of complex number
16. 	public int Im() {
Return type of method must be float.
17. 	return y;}
18. }
19. //subclass of Complex that includes methods for
20. //writing to real and imaginary parts of complex numbers
21. class BComplex implements Complex{
Replace "implements" with "extends".
22. 	//method for assigning to real part of complex number
23. 	public void setRe(float r){
24. 		x = r;
25. 		return null;
Cannot return a value when return-type is void; remove the "null".
26. 	}
27. 	//method for assigning to imaginary part of complex number
28. 	public void setIm(float i){
29. 		y = i;
30. 		return;
31. 	}
32. }
33. //client class
34. class testComplex{
35. 	public void main(String arg) {
The main() method must be static: "public static void".
37. 		Complex c = new BComplex(1.0f,2.0f);
Constructors are not inherited.  Class BComplex needs a constructor:
          public BComplex (float r, float i) { super(r,i); }
38. 		c.setRe(3.0);
Compiler will complain since c is a reference of type Complex which does
not have a method setRe().  Use ((BComplex) c).setRe(3.0);
39. 		System.out.println(c.x);
40. 		System.out.println(c instanceof BComplex);
41. 	}
42. }

Problem 3

The program below computes the frequencies of values (>0) in an array of array of int (AAI) (sometimes called multi-dimensional arrays), and prints a histogram.

The AAI is initialized to the following values:
1st row: 2
2nd row: 5, 4
3rd row: 4, 5, 4

A frequency table is computed for the AAI, i.e. how many times a particular value occurs in the AAI. In our case the frequency table computed would look like this:

Value:     0 1 2 3 4 5
Frequency: 0 0 1 0 3 2

The histogram based on these frequencies would look like this:

    *
    **
  * **
012345

i.e. each "bar" in the histogram has number of "stars" equal to the frequency of the value indicated below the bar. The next few pages show skeleton code for a class called ArrayOfArrays. You need to complete this skeleton code, without modifying any code given to you, by answering 7 short questions numbered (a) through (g).

public class ArrayOfArrays {

	public static void main(String args[]) {
		// Creates an AAI which has 3 rows.
		int[][] values = new int[3][];
		
// (a) (4 points)
		// Write code which creates the following structure for the AAI:
		// 1st row of length 1, 2nd of length 2 and 3rd of length 3.

for (int i = 0; i < values.length; i++)
	values[i] = new int[i+1];


// (b) (3 points)
		// Write code to initialize the rows of the AAI as follows:
		// 1st row: 2
		// 2nd row: 5, 4
		// 3rd row: 4, 2, 4
		
values[0][0] = 2;
values[1][0] = 5; values[1][1] = 4;
values[2][0] = 4; values[2][1] = 2; values[2][2] = 4;
		
		
		
		// Computes the frequencies and prints the histogram
		int[] frequencies = computeFrequencies(values);
		printHistogram(frequencies);
		
// (c) (3 points)
		values[0] = values[2] = values[1];
		// What will the following statement print?
		// The code for method printValues appears below.
		printValues(values);
		
The assignment statement above causes all the rows to reference the same
data.  Thus the printout will be:
54
54
54	
			
	} //end of main method

	// Prints an AAI.
	public static void printValues(int[][] anAAI) {
		for (int i = 0; i < anAAI.length; i++) {
			for (int j = 0; j < anAAI[i].length; j++)
				System.out.print(anAAI[i][j]);
			System.out.println();
		}
	}
	
// (d) (3 points)
	// Write a method to compute the max value in a non-empty array of int.
	public static int findMax(int[] anIntArray) {
int max = anIntArray[0];
for (int i = 1; i < anIntArray.length; i++)
	if (max < anIntArray[i]) max = anIntArray[i];
return max;
	
	
	
	} // end method

// (e) (4 points)
	// Write a method to compute the max value in an AAI.
	public static int findMax(int[][] anAAI) {
int max = findMax(anAAI[0]);
for (int i = 1; i < anAAI.length; i++) {
	int maxInRow = findMax(anAAI[i]);
	if (max < maxInRow) max = maxInRow;
	}
return max;
	
	} // end method
	
// (f) (8 points)
	// Write a method to compute the frequencies of values in an AAI.
	// Assume all values in the AAI are greater or equal to 0.
	// The method should return an array of int containing the frequencies.
	public static int[] computeFrequencies(int[][] anAAI) {

int[] frequencies = new int[findMax(anAAI)+1];
for (int i = 0; i < anAAI.length; i++)
	for (int j = 0; j < anAAI[i].length; j++)
		++frequences[anAAI[i][j]];
return frequencies;
	
	} // end method
	
// (g) (10 points)
	// Write a method to print the histogram, assuming that the values
	// in the AAI are between 0 and 9. For example,
	// given the present data, it should print the following:
	//     *
	//     **
	//   * **
	// 012345
	public static void printHistogram(int[] anIntArray) {
	
for (int max = findMax(anIntArray); max > 0; max--) {
	for (int j = 0; j < anIntArray.length; j++)
		if (anIntArray[j] >= max) System.out.print("*");
		else System.out.print(" ");
	System.out.println();
	}
for (int j = 0; j < anIntArray.length; j++)
	System.out.print(j);
System.out.println();
	
	} // end method
}//end of class ArrayOfArrays

Problem 4

Write the body for the power method which calculates aⁿ:

public static long power (long a, in n)  { /* code omitted */ }

You may assume that n > 0. Your method must calculate aⁿ recursively in O(log n) time. No points will be awarded for solutions which don't fit the time bound.

public static long power (long a, int n)  {
	// Base case
	if (n == 0) return 1;
	if (n == 1) return a;

	// We recursively compute a^(n/2)
	long a2 = power(a,n/2);
	if (n % 2 == 0)		// If n is even...
		return a2*a2;
	else			// Else n is odd...
		return a2*a2*a;
	}

Problem 5

Using words and pictures (no Java code, pseudo-code is OK), carefully explain how to insert an Object x into a doubly linked list given a reference to the node before the insertion point.

Numbers refer to the picture below. We first (1) create a new node and initialize its data field. Let n be the reference to the node before the insertion point. We set the next (2) and previous (3) pointers of our new node to point at n.next and n, respectively. We set the previous pointer (4) of n.next to point at our new node. Finally, we set the next pointer (5) of n to point at our new node.

Problem 6

Write a Java class called ArrayQueue that implements the following interface with a "circular array." You may assume that there is an upper bound (positive!) to the maximum number of elements in the queue at any one time. As long as the number of elements in the queue does not exceed the maximum, the queue should be able to be used indefinitely. You may also assume that the enqueue and dequeue operations won't fail because of overflow or underflow, respectively. You must use an array.

public interface Queue {
	boolean isEmpty ();		// True iff queue has no elements
	boolean isFull ();		// True iff queue has reached max size
	void makeEmpty ();		// Removes all elements from queue
	void enqueue (Object x);	// Adds the object to the rear of queue
	Object dequeue ();		// Removes an object from front of queue
	}
public class ArrayQueue implements Queue {
	/* Without care, the front and last values for a full queue can
	 * look just like the front and last values for an empty queue.
	 * This version keeps count of the number of elements in order
	 * to distinguish full from empty.  You can also resolve this without
	 * using a count, by making "full" be one less than completely full.
	 */
	private int front;		// First valid element in queue
	private int last;		// Last valid element in queue
	private int count;		// Number of elements in queue
	private Object[] queue;		// The queue itself
	
	public ArrayQueue (int maxElements) {
		queue = new Object[maxElements];
		makeEmpty();
		}
		
	public boolean isEmpty () {
		return count == 0;
		}
		
	public boolean isFull () {
		return count == queue.length;
		}
		
	public void makeEmpty () {
		count = 0;
		front = 0;
		last = -1;
		}
		
	public void enqueue (Object x) {
		last = (last+1)%queue.length;
		queue[last] = x;
		count++;
		}
		
	public Object dequeue () {
		Object temp = queue[front];
		front = (front+1)%queue.length;
		count--;
		return temp;
		}
	}

Problem 7

Briefly describe the stack data structure and the two fundamental operations for manipulating a stack. (Do not write full Java code.)
A stack is a LIFO (last-in first-out) data structure. Push puts a new item on top of the stack and pop removes the top item from the stack.
We can use a stack to evaluate an expression in postfix form. Show the stack at each phase during the evaluation of the following postfix expression. At the end of the algorithm, the result should be left on the stack.
```
 1 2 3 * 4 - 12 6 / 7 * + +
```
```
Stack: 1
Stack: 1 2
Stack: 1 2 3
Stack: 1 6
Stack: 1 6 4
Stack: 1 2
Stack: 1 2 12
Stack: 1 2 12 6
Stack: 1 2 2
Stack: 1 2 2 7
Stack: 1 2 14
Stack: 1 16
Stack: 17
```