CIT 594 Midterm Spring 2005, Dave Matuszek (Answer Key)
1. (5 points) Write a short recursive method to count the number of nodes (self and all descendants) in a binary tree rooted at `node.` Assume you have methods `getLeftChild()` and `getRightChild()`. I've started it for you:
 ```int countNodes(BinaryTree node) { if (node == null) return 0; return 1 + countNodes(node.getLeftChild( )) + countNodes(node.getRightChild( )); }```

2. (3 points) What is the time required (using Big-O notation) to execute the method in the previous question? (Use `n` = number of nodes) as the "size" of the problem).
O(n)

3. (3 points) If we use` n `to mean the depth of the tree in question #1 (that is, how far it is from node to its deepest descendant), and we assume that the tree is balanced, what is the time required (using Big-O notation) to execute the method in question #1?
O(2n) (in case this doesn't display properly, it's 2 to the power n)

4. (4 points) A `Vector` has methods` int size() `and``` int capacity()```. What is the difference?
1. `size() `returns:
The number of elements currently in the Vector

2. `capacity() `returns:
The number of elements the Vector can hold before it needs to be expanded.

5. (5 points) We haven't yet studied linked lists, but all you need to know is that `LinkedList` implements `Iterator`. Write a loop to print all the elements of a `LinkedList` named `myList`.
 ```Iterator iter = myList.iterator( ); // using a while loop while (iter.hasNext( )) { System.out.println(iter.next( )); }``` ```// using a for loop for (Iterator iter = myList.iterator( ); iter.hasNext( ); ) { System.out.println(iter.next( )); }``` ```for (Object o : myList) { // using Java 5's enhanced for loop System.out.println(o); }```

6. (12 points) True or false (`T` or `F`):
1.  T  Java uses a stack to implement recursive methods.
2.  T  Java uses a stack to implement non-recursive methods.
3.  T  A `Stack` has both `empty()` and `isEmpty()` methods.
4.  F  If you override` equals(Object)` you must also override `hashCode()`.
5.  T  If you override `hashCode()` you must also override `equals(Object)`.
6.  F  If you implement `Observer` you must have a class that extends `Observable`.
7.  F  If you extend `Observable` you must have a class that implements `Observer`.
8.  F  HTML tags are case sensitive.
9.  T  You can put bulleted lists in a Javadoc comment.
10.  F  No two objects in a hash table may have the same hash code.
11.  T  Only `String` parameters can be passed to an applet.
12.  T  Only the Java compiler, not the runtime, uses generic type information.

7. (8 points) What are Dr. Dave's four rules for doing recursion?
 Do the base cases first. Only recur with a simpler case. Don't modify global variables or objects. Don't look down.

8. (5 points) Draw lines to match up the Collection operations with the corresponding set operations:
 `containsAll(Collection c) •` containsAll --> subset `•` union `addAll(Collection c) •` addAll --> union `•` intersection `removeAll(Collection c) •` removeAll --> difference `•` difference `retainAll(Collection c) •` retainAll -> intersection `•` member `contains(Object e) •` contains -> member `•` subset

9. (3 points) Why is the following code undesirable in a JUnit test method?
 ``` try { leafB2.setLeftChild(rootAB); fail(); } catch (IllegalArgumentException e) { System.out.println("This call would form a loop."); }``` Because test methods that succeed shouldn't produce any output.
10. (8 points) Give the complete signature and the return type of four methods specified by the `Collection` interface, other than the ones mentioned in the previous question. (Use the form return_type name(arg_types) ). Do not give more than four.
 ```boolean add(Object o) void clear( ) boolean equals(Object o) int hashCode( ) boolean isEmpty( )``` ```Iterator iterator( ) boolean remove(Object o) int size( ) Object[] toArray( ) Object[] toArray(Object[] a)```

11. (8 points) Give the complete signature and the return type of four methods specified by the `Map` interface. (Use the form return_type name(arg_types) ). Do not give more than four.
 ```void clear( ) boolean containsKey(Object key) boolean containsValue(Object value) Set entrySet( ) boolean equals(Object o) Object get(Object key) int hashCode( ) ``` ``` boolean isEmpty( ) Set keySet( ) Object put(Object key, Object value) void putAll(Map t) Object remove(Object key) int size( ) Collection values( )```

12. (5 points) Rewrite the following class to use generics. Do not assume that `x` and `y` are the same type.
 `public class Pair { private Object x; private Object y; public Pair(Object x, Object y) { this.x = x; this.y = y; } public Object getX() { return x; } public Object getY() { return y;}}` `public class Pair { private X x; private Y y; public Pair(X x, Y y) { this.x = x; this.y = y; } public X getX( ) { return x; } public Y getY( ) { return y;}}`

13. (3 points) Using your generic class from the previous question, define a typesafe variable `myPair` with components of type `Integer` and `Double`, and assign some reasonable value to it.

Pair<Integer, Double> pair = new Pair<Integer, Double>(5, 23.5);

14. (3 points) The following code zeros out an array. In the space provided, write a suitable loop invariant.
 ```for (int i = 0; i < myArray.length; i++) { myArray[i] = 0; // loop invariant: For all j <= i, myArray[j] == 0 }```

15. (2 points) `log2 100` is between  6  (next lower integer) and   7  (next higher integer).

16. (4 points) Mention one way you can use a `HashMap` without writing your own `hashCode()` method.
Use only Strings as keys.
Or, use keys for which == is an appropriate equality test.

17. (4 points) Why is clustering less of a problem with a bucket hash than with an open hash?

With an open hash, the larger a cluster gets, the more likely it is for new keys to hash into it, making the cluster larger. For a bucket hash, the size of the cluster does not affect the probability that new keys will hash into it.

18. (5 points) Define a singleton class (a class having only one instance) named `Add`. `Add` should have a factory method `makeAdd()`, no other methods, and no instance variables. Write the complete class definition.
 ```public class Add { static Add add = new Add( ); private Add( ) { }; public static Add makeAdd( ) { return add; }```

19. (5 points) In Java, a hex number has the syntax `0x`digits or `0X`digits, where digits is one or more hexadecimal digits (case insensitive). Write a BNF definition (simple or extended, your choice) for a hex number; do not worry about limiting the number of digits.

<hex number> ::= 0x<hex digits> | 0X<hex digits>

<hex digits> ::= <hex digit> { <hex digit> }
OR
<hex digits> ::= <hex digit> | <hex digit><hex digits>

<hex digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | a | b | c | d | e | f | A | B | C | D | E | F

20. (5 points) Write a recognizer for hex numbers, based on your answer to the previous question. Assume you have already written a `boolean hexDigit()` method.
 ```boolean hexNumber( ) { // There are many possible variations on this method; // I've graded it mostly on whether the logic is correct if (!digit("0")) return false; if (!letter("x") && !letter("X")) return false; if (!hexDigit( )) return false; while (hexDigit( )) { } return true; }```