CS230 Data Structures, Wellesley College, Fall 1999

Problem Set 9 (Optional)

Due anytime before Wednesday, December 22

[CS230 Home Page] [Assignments] [Documentation] [Software Installation] [FAQ] [CS Dept.] [CWIS]

 

This problem set is optional. You are required to know the material on this assignment, but you need not turn it in. If you do turn it in, it can only help your grade and not hurt it.

Below are two of the three problems on the assignment. The third problem (on hash tables) will be posted in the future.


Reading

Reading Notes:

Code

Problems 2 and 3 require writing Java programs. All the code for this assignment can be found in the Tables folder of ps9_programs in the CS230 download folder.


Problem 1: Diagramming Heaps

Recall that heapsort is a sorting algorithm with the following two stages:

  1. Create a priority queue and enqueue all the elements to be sorted.
  2. Repeatedly dequeue elements from the priority queue until it is empty. The order of the dequeued elements will be sorted from high to low according to the comparator of the priority queue.

The reason that the algorithm is called heapsort is that a priority queue is commonly implemented as a "heap" data structure. But the algorithm works for any implementation of priority queues, even ones that don't use the heap data structure.

In class, we studied two kinds of heaps: (1) complete heaps and (2) leftist heaps. The following parts ask you to show the sequence of intermediate heaps that would arise when running the heapsort algorithm with these two kinds of heaps on the following letters:

H E A P S O R T

In both examples, you should assume that the Comparator for the heap treats letters later in the alphabet as being "greater" than ones earlier in the alphabet. Thus, sorting the above letters should yield:

T S R P O H E A

Part a.

Show the intermediate heaps constructed when using a complete heap to perform heapsort on the letters:

H E A P S O R T

You should show the state of the heap after each (1) enqueue operation and (2) dequeue operation. (You need not show intermediate heaps that arise during the middle of one of these operations.)

You should draw each heap as a complete binary tree whose nodes are letters. Remember that letters later in the alphabet should be on top.

Part b.

Show the intermediate heaps constructed when using leftist heaps to perform heapsort on the letters:

H E A P S O R T

You should show the state of the heap after each (1) enqueue operation and (2) dequeue operation. (You need not show intermediate heaps that arise during the middle of one of these operations.)

You should draw each heap as a binary tree whose nodes contain (1) a letter and (2) the rank of the node. Recall that the rank of a node is the length of its right spine.


Problem 2: Implementing Tables as Mutable Binary Search Trees

In this problem you will implement a table as an object with the following three instance variables:

  1. A MutableObjectTree bst containing a binary search tree in which values are instances of the TableEntry entry class ordered by their keys. Rather than pointing directly at the root of the tree, bst points a dummy header node whose left subtree is the root of the binary search tree (see the pictures below). The dummy header node simplifies many operations by guaranteeing that every node in the binary search tree (including the root) has a parent. The value and right subtree of the dummy header node are irrelevant and so can be arbitrary.
  2. An integer size that holds the number of elements in the table. This variable is not strictly necessary, since it could be calculated as the number of nodes in the binary search tree. However, it is much more efficient to have the size stored as an instance variable than to calculate it every time it is neeed.
  3. A Comparator comp that holds the comparator used for comparing keys in the table.

To illustrate the desired structure of the table, we consider a concrete example that is used as part of the test cases. Suppose that T is the result of new TableMutableBST. Then its object diagram is:

Executing T.insert("Emil", "3456") changes this to:

After T.insert("Viola", "5678"), this becomes:

After T.insert("Abby", "1234"), this becomes:

After T.insert("Bud", "2345"), this becomes:

After T.insert("Sam", "4567"), this becomes:

Finally, after insert("Emil", "6789"), this becomes:

The MutableObjectTree class is just like the ObjectTree class except that the components of a node can be mutated via the setValue, setLeft, and setRight methods. Here is a list of all the methods supported by the MutableObjectTree class:

public static MutableObjectTree leaf()
public static boolean isLeaf(MutableObjectTree t)
public static MutableObjectTree node(Object v, MutableObjectTree l, MutableObjectTree r)
public static Object value (MutableObjectTree t)
public static MutableObjectTree left (MutableObjectTree t)
public static MutableObjectTree right (MutableObjectTree t)
public static void setValue (MutableObjectTree t, Object newValue)
public static void setLeft (MutableObjectTree t, MutableObjectTree newLeft)
public static void setRight (MutableObjectTree t, MutableObjectTree newRight)

To do this problem, you should flesh out the skeleton in the file TableMutableBST in the Tables folder of the ps9_programs folder. You will need to implement the following seven table methods:

public void insertEntry (TableEntry entry)
Inserts the entry into this table. Any existing entry with entry.key as its key is effectively overwritten to have entry.value as its value. This method is equivalent to insert(entry.key, entry.value), where insert() is the two-argument insertion method presented in class.

public Object lookup (Object key)
Returns the value associated with key in this table, or null if there is no such value.

public void delete (Object key)
Removes the entry indexed by key from this table. Has no effect if the key is not in this table.

public int size()
Returns the number of key/value assocations in this table.

public void clear()
Removes all key/value pairs from this table.

public Object clone()
Returns a copy of this table. Operations on the copy should not affect this table, and vice versa.

public ObjectList toList()
Returns a list of the entries of this table in sorted order.

Additionally, it is very helpful to have an auxiliary method find() for finding the position of a key in a binary search tree. The insertEntry(), lookup(), and delete() methods can all be simplified using the find() method. The find() method returns a instance of the FindInfo class, which is defined as follows. (You have been provided with a definition of this class in the Table folder.)


public class FindInfo { public MutableObjectTree parent, child; public boolean isChildToLeft; public FindInfo (MutableObjectTree parent, MutableObjectTree child, boolean isChildToLeft) { this.parent = parent; this.child = child; this.isChildToLeft = isChildToLeft; } }

Here is the contract for the find() method:

public FindInfo find (Object key,
                       MutableObjectTree parent, 
                       MutableObjectTree child, 
                       boolean isChildToLeft)

Assume that parent is the parent node of child and that isChildToLeft is true if child is the left subtree of parent and false if child is the right subtree of parent. Returns a findInfo instance describing result of looking for key in the mutable binary search tree child. Suppose that the resulting instance of findInfo is named result. Then the meaning of the components of result is as follows:

As a simple test of your implementation, run the TestTable applet and select TableMutableBST. You may want to compare your output with that of the TableSortedVector implementation that is also provided in the table folder.

Notes:

Submission Details: For your softcopy submission, turn in TableMutableBST.java.For your hardcopy submission, turn in TableMutableBST.java and a copy of the transcript of the test cases. If necessary, you should reformat the transcript so that all the information is visible on the printed version (i.e., no lines should fall off the right edge of the page).

 
Problem 3: Implementing Tables as Hash Tables

This problem is still under construction.