Name: ________________________________

CSE373 Spring Quarter
University of Washington
Midterm #2 with notes and answers
May 13, 2005
Closed book, closed notes, closed neighbor; no calculators
2 points per part except as noted

 
. (3 pts.)
Draw (as a tree) the heap that results from adding the following values, in the order given, to an initially empty heap:

5   9   2    4   16   12   1

 
root: 1

across the bottom: 9 16 12 5
 
 
.  (3 pts.)
Draw the binary search tree that results from adding the following values, in the order given, to an initially empty binary search tree

5   9   0    4   16   12   99   3   

 
root: 5

left subtree in-order:  0 3 4

right subtree in-order: 9 12 16 99
 
 
. (3 + 7 pts.)
One way to measure how well a hash table is organized is to compute the total number of collisions divided by the total number of objects stored.  Let's call this the "synonym ratio".  A special case: if there are no objects in the table, the ratio is defined to be 0.0.  In the definition, "Total number of collisions" means the the number of objects which hash to the same index as some other object.

A. Suppose in a particular case, the values stored are these strings:

"a", "abba", "baba", "egg", "due", "dude", "gone", "Klondike Annie"

Suppose the hash function is the length of the string (mod table size), and the table size is 10.  Calculate the synonym ratio.

7 collisions (including "Klondike Annie", which maps to index 4), 8 objects stored, so ratio is 7/8.  

B. Suppose the hash table is implemented with separate chaining in a class called HTable.  I.e., there is an array of linked lists, with the list at each array index containing all the objects which hash to that index.  (The lists may be null if appropriate.)  Let's say the array is declared as this instance variable:

private List[] entries;

Using only this information, implement the calcSRatio method of HTable, which returns the synonym ratio as defined above.

public double calcSRatio() {

int totalObjects = 0;

int duplicates = 0;

for (int i = 0; i < entries.length; i++) {

     if (entries[i] != null && entries[i].size() > 0) {

         totalObjects += entries[i].size();

         if (entries[i].size() > 1) {

              duplicates += entries[i].size();

         }

     }

}

if (totalObjects > 0) return (double) duplicates / (double) totalObjects;

else return 0.0;

}    
Main grading points for B:
  • check for null lists
  • correct calculation of the total number of objects
  • correct calculation of the total number of collisions
  • check to avoid division by 0
  • answer calculation
  • answer return
  • general Java and programming mechanics
 
 
.  (3 pts.)
State a "good" (standard, works well in practice) hashing function for strings, and illustrate by showing how the hash of "ego" would be calculated.

Treat the characters of the string as coefficents of a polynomial in a base like 31, with each character converted to its numerical equivalence (Unicode value).  For example, "ego" would be

(e * (31**2))  + (g*31) + o

This is the method used for the Java String hashCode().

 
Before being used as an index, the has code would be modded by the table size; this didn't have to be mentioned explicitly, since it is normally assumed as the last step of an index calculation.

Grading points:  A good function should be

  • computationally efficient
  • incorporate each char's position
  • incorporate each char's value
  • use "good" constants for modulus and base (e.g., 31 or 37, etc instead of 2 or 256)
  • achieve a good distribution (spread) of values
  • avoid collisions 
 
 
. 
Assume all the key values in a (min) heap are distinct.  If the heap has a size greater than one, where is the largest value?
  1. can be anywhere
  2. must be at depth 1 (the level just below the root)
  3. must be at the lowest level
  4. must be a leaf, though not necessarily at the lowest level
must be a leaf.  Not quite right to say "at the lowest level" 
 
 
. 
Given this binary search tree, show the tree that results from deleting the node indicated.  Use the "left hand" rule.

 

 
75 is promoted into the 100's old position, and the right child of 50 now points to 66 
 
. (3 pts.)
A repeating sequence of numbers

1  2  3  1  2  3  ...

is added to an initially empty binary search tree (values <= go on the left).   Let N be the number of nodes in the tree at any given point.  If N > 1, what is the height of the tree?
  1. log3N
  2. log3N +1
  3. log3N -1
  4. N/3
  5. N/3 + 1
  6. N/3 - 1
  7. N%3
  8. N%3 + 1
  9. N%3 - 1  
  10. other: _________                
If you had a different but still linear formula in N, only one point was deducted. 

The first thing to do with a problem like this is to draw the tree!  After not too long you would begin to notice that the tree grows one level deeper when a "3" is added, and only then, i.e., on every third input value.  This should suggest that the answer is closely related to dividing by 3.

Next you might make a table with three columns: value added, N, height.  Since you suspect that /3 is important, you might make a column with N/3, too.  The relationship between the /3 and the height column should then become obvious.
 
. 
In a binary search tree, when a node with one child is deleted, how many pointers have to change?
  1. 0
  2. 1
  3. 2
  4. 3
  5. more than 3
1.  Make the deleted node's parent point to the deleted node's child instead.
 
. (3 pts.)
Consider this claim: If a binary search tree is complete, then is it also height-balanced (i.e., an AVL tree).

You may assume the tree has at least one node.

If the claim is false, give a counterexample (an example which shows that the claim is false).

If the claim is true, prove it (or at least explain carefully).

True.  If a tree is complete, then all levels except possibly the lowest are full.  Thus, its leaves are at the lowest level or the level just above that, so leaf levels differ by at most 1.  Thus, any sibling subtrees have heights that differ by at most 1.
 
 
. (8 pts.)
The class PQueue implements a priority queue (min queue) and has the following public methods (only):

PQueue(); //create a new, empty priority queue

Object delMin(); //delete and return the highest-priority value, or null if the queue is empty.  Objects in the queue must have a suitable compareTo method.

void add(Object newObj); //add a new value to the queue; exception if the object is null or the queue is full.

Using PQueue, implement a NlogN sort.  You may assume that the objects being sorted have a suitable compareTo method.  Except for arrays and Object, don't use any classes except PQueue.  

/** Sort the array in ascending order.
@param input a non-null array of non-null Objects, which can be compared to one another using their compareTo method.
@return an array containing exactly the same objects as the original array, except arranged in ascending order.
*/
Object[] sort(Object[] input) {

Object heap = new PQueue();

for (int ob = 0; ob < input.length; ob++) {

   heap.add(input[ob]);

}

Object[] answer = new Object[input.length];

for (int ob = 0; ob < input.length; ob++) {

  answer[ob] = heap.delMin();

}

return answer;

}
This is a variant of Heapsort.  The "real" heapsort works on the array directly, bubbling down the elements right to left starting from the middle.  Our version using the PriorityQueue ADT is a little slower, but is still NLogN.

You could use the input array to hold the output.  Many programmers consider it better practice to use a separate array unless the documentation says otherwise (no points off).  Most APIs would make this explicit in the documentation. 

It is not necessary to check for exceptions on the add method, since the input is guaranteed to be non-null, have proper compareTo, etc.  But it is not harmful to do so.

Main grading points:

  • creating a heap
  • building the heap from the input array
  • building an output array from the heap
  • returning the answer
  • general Java and programming mechanics