COP 3530                 Exam 2              August 15, 2000

Kraynek                                      Name:________________

15 points
1. Write a Java main class to read a file named Problem1.txt and output to the screen all the
unique words in the file in alphabetic order along with the number of times each appears in
the file. You can use only Java classes. Assume the String DELIMITERS has been defined.
10 points
2 Suppose we have an open hash table with size buckets implemented using the Java
LinkedList class. Let h(x) be the hash code function for the Object x. Write a method
     boolean contains(Object x);
for the open hash table that returns true if x is in the table and false otherwise.
10 points
3.a.  Suppose we have a closed hash table with 10 buckets. Show the contents of the bucket
array after the following are inserted using quadratic resolution of collisions. 
     14, 23, 17, 33, 11 3
b. Show the array after rehashing by doubling the size of the table.
15 points
4. Write the method 
     void pushUp(int n);
that pushes n up in a BinaryHeap. Assume that the root is a position 0 in the array.

10 points
5. Let A = { 10, 2, 9, 7, 11, 3, 8, 6 }. Show the array after heapifying it.
10 points
6. There are two ways to build a heap of n elements.
     1. insert n elements using the BinaryHeap insert method.
     2. add the n elements and then heapify the array.

a). What is the running time of method 1?
b). What is the running time of method 2?
c). Why is method more efficient than the other? You can give an intuitive argument rather
than a mathematical one.

10 points
7. Suppose the array Sets = { -4, 0, 1, 2, 2, -3, 5, 6, 6, -1 } represents the Disjoint Sets
array. Show the resulting array after the following operations ( using union by rank and path
compression in the gets ) are performed:
     int A = get(3);
     int B = get(8);
     union(A,B);
10 points
8. Given the following graph, show the distance and previous field after Dijkstra's shortest
paths algorithm is run using 0 as the start vertex.

10 points
9. Given the array A = { 8, 5, 9, 11, 15, 12, 4, 7, 3 }, show the partitioned array after one pass of the
quicksort algorithm using the median of 3 for the pivot