CIT594 Midterm Exam Spring 2011 Name     ______    Answers & Rubric     ______

Please keep all your answers short and to the point. Do not provide extra information that was not asked for. Where Java code is requested, minor syntax errors will be forgiven.

1. We will define a simple number as either a unsigned integer, or an unsigned real number with no exponent. Example simple numbers are:` 25`,` 3.5`,` 177.`, and` .0003`.

1. (5 points) Write a complete BNF definition of “simple number”.

<simple number> ::= <integer> | <integer> . [<integer>] | [<integer>] . <integer>
<integer> ::= <digit> {<digit>}
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

2. (5 points) Write a regular expression to match simple numbers (and nothing else).

\d+|\d+\.\d*|\d*\.\d+                   (plain regular expression)
"\\d+|\\d+\\.\\d*|\\d*\\.\\d+"     (Java string version)

2. (5 points) What are the instructor’s rules for recursion?

Handle the base case(s) first.
Recur only with a simpler case.
Don't both read and modify a global variable.
Don't look down.

3. (10 points) Here are some statements about an array, partway through sorting it:
1. There is a part of the array in which all values are in their correct and final place.
2. There is a part of the array in which all values are in the correct order, relative to one another.
3. There is a part of the array in which all values are smaller than in another part of the array.
For each of the following sort algorithms, choose the statement that best describes the array (fill in the correct letter from above).
1. _A_ Bubble sort
2. _A_ Heapsort
3. _B_ Insertion sort
4. _C_ Quicksort
5. _A_ Selection sort

4. Class ` BinarySearchTree<Integer> `defines a binary search tree for integers (smaller or equal numbers to the left, larger numbers to the right). The value, left child, and right child of a node` n `can be accessed with the functions `n.value()`,` n.leftChild()`, and` n.rightChild()`, respectively.

1. (5 points) Write a recursive method to return the largest integer in a `BinarySearchTree`.

`int largest(BinarySearchTree<Integer> root) {`
if (root.rightChild() == null) return root.value();
else return largest(root.rightChild());
}

2. (5 points) Write a recursive method to print out all the numbers in the given `BinarySearchTree` in reverse order (that is, largest to smallest).

`void printRev(BinarySearchTree<Integer> root) {`
if (root == null) return;
printRev(root.rightChild());
System.out.println(root.value());
printrev(root.leftChild());
}

5. (5 points) Write a recursive LOL function to compute the factorial of a positive integer. Call the function to compute the factorial of 10, and tell the user the result.

define factorial [x] if less-than? x 2 1 times x factorial minus x 1
tell factorial 10

6. (5 points) What are the three methods in the `Iterator` interface? (Give complete signatures.)

boolean hasNext()
E next()
void remove()

7. Consider the following method:
```    boolean hasDuplicates(int[] array) {
for (int i = 0; i < array.length; i++)
// loop invariant for part (c)goes here
for (int j = i + 1; j < array.length; j++)
if (array[i] == array[j]) return true;
return false;
}```
1. (5 points) Using Big-O notation, what is the running time of this algorithm? Briefly defend your answer.

O(n2). Worst case, outer loop executes n times (n = length of array),
inner loop executes n/2 times, so O(n * n/2) = O(n2/2) = O(n2).

2. (5 points) Describe (in English; don’t write code) a faster algorithm to test an array for duplicates.

1. O(n): Create a HashSet. For each element, if it is in the HashSet, stop and return true, otherwise put it in the HashSet. If all elements are successfully put in the HashSet, return false.
2. O(n): Convert the array to a list, then convert the list to a HashSet (can't be done in one step), then compare the size of the set to the size of the array.
3. O(n log n): Same as A, but use a TreeSet (which is implemented as a binary search tree) instead of a HashSet. However, bad input could make this O(n2).
4. O(n log n): Sort the array, using an O(n log n) sort. Compare each pair of adjacent elements for equality. (Side effect: modifies the array!)

3. (5 points) What is the loop invariant for the outer loop? State it formally if you can, but an informal statement, if sufficiently precise, will also be acceptable.

Correct: For all a < i and b < array length, if a != b, then array[a] != array[b]
(It isn't enough to say that some one element is different from all the others)

8. (5 points) If you define a class `Employee`, and you want to use `Employee` objects as keys into a `HashMap`, what two methods must you define? (Give complete signatures.)

integer hashCode()
boolean equals(Object o)

9. (5 points) In order to put `Employee` objects into a `TreeSet`, what interface must `Employee` implement, and what method must you define (give complete signature)?

Implement Comparable, define int CompareTo(Employee e)   -OR-
Implement Comparator, define int compare(Employee e1, Employee e2), boolean equals(Object o)

10. (5 points) Suppose `set` is a `TreeSet<String>`. Write a Java statement or statements (not a complete function) to create a `LinkedList<String> list` containing all the elements of `set`.

11. (5 points) Name two garbage collection algorithms, and list one disadvantage of each.

Reference counting -- when objects reference each other, they can never be garbage collected.
Mark and sweep -- entire program must stop while garbage collection occurs.

12. (5 points) Give a precise statement of what it means to say that a binary tree is balanced.

The difference in depth between any two leaves is never greater than 1.
A binary tree of depth d must have at least 2d nodes.
In a binary tree of depth d, every node at level d-2 and above has two children.

13. (10 points) Briefly but precisely, define each of the following terms:

A function used to provide a different interface to an existing function.

2. Branching factor of a tree
The average number of children of non-leaf nodes in the tree.

3. Serialization
(Also called marshalling) Converting data into a linear sequence, usually for transmission.

4. Heap (as in Heapsort)
A left-justified, balanced binary tree in which every node has the heap property (that is, it has no children holding a larger value).

5. Heap (as in storage management)
A data structure to support requests for blocks of memory by a running program.

14. (5 points) Is Java's `LinkedList` class implemented using singly-linked lists or doubly-linked lists? Tell why you think your answer is correct.

Doubly-linked, because a ListIterator can move both forwards and backwards on the list.