CS230 Data Structures, Wellesley College, Fall 1999

Problem Set 7

Due any time Friday, November 12

## Exam 2 Announcement

On Friday, November 12, the second take-home exam will be posted. It will be due at 11:59pm on Tuesday, November 23, so that you will have two weekends to work on the exam. The exam will emphasize the material covered on Problem Sets 5 through 7: the use of standard abstract data types: (lists, binary trees, Rose trees, stacks, queues, priority queues, sets, and bags); the implementation of these ADTs in terms of vectors, arrays, and lists; and algorithmic complexity (asymptotic notation, recurrence equations, worst and best case analysis, etc.).

There will be two more problem sets after the exam. Problem Set 8 will be posted on Tuesday, November 23, and will be due on Friday, December 3. Problem Set 9 will be posted on Thursday, December 2, and will be due on Friday, December 10.

## Problem 1: Binary Tree Enumerations

This problem asks you to understand some code, but requires no programming.

We have seen before that it is possible to extract a list of values from a binary tree. In lecture, we discussed methods called preOrderList(), inOrderList(), and postOrderList() for collecting the elements of a binary tree into a list in the order specified by a tree traversal. For certain kinds of problems, we do not want to extract all of the values from a tree at once; rather, we want to extract them one at a time on an as-needed basis. That is, we would like some sort of Enumeration on a tree that enumerates the next value every time one is requested. If the tree is large, this approach can be more efficient than trying to immediately make a list of all the values, especially if we do not plan to examine all of the values in the tree.

Below is a TreeEnumeration class that implements this behavior. As with all Enumerations, it provides a hasMoreElements() method that indicates if there are more elements to be enumerated, and a nextElement() method that returns the next value of the enumeration. The first parameter to the constructor method is the tree whose values we want to enumerate. The second parameter to the constructor method is a Collection that controls the order in which the values of the tree will be enumerated.

```import java.util.Enumeration;

public class TreeEnumeration implements Enumeration {

private Collection collection;

public TreeEnumeration (ObjectTree tree, Collection c) {
collection = c;
insertIfNotLeaf(tree);
}

public boolean hasMoreElements()  {
return !collection.isEmpty();
}

public Object nextElement() {
if (collection.isEmpty()) {
throw new TreeException("Attempt to nextElement() on an empty TreeEnumeration.");
} else {
ObjectTree tree = (ObjectTree) collection.deleteFirst();
// tree is guaranteed not to be a leaf here.
insertIfNotLeaf(ObjectTree.left(tree));
insertIfNotLeaf(ObjectTree.right(tree));
return ObjectTree.value(tree);
}
}

public void insertIfNotLeaf (ObjectTree tree) {
if (! ObjectTree.isLeaf(tree)) {
collection.insert(tree);
}
}

}
```

We can test an enumeration via the following testEnumeration method, which prints out the enumerated values one by one:

```	public void testEnumeration(Enumeration elts) {
try {
while (elts.hasMoreElements()) {
System.out.println(elts.nextElement());
}
} catch (TreeException e) {
println("TreeException: " + e.getMessage());
}
}```

(Here, try/catch is the means in Java of catching and handling exceptions. Since we have not covered this in class, you are not required to understand the details, though if you are curious you should read up on the topic of exception handling.)

Suppose that testTree is a tree whose printed representation is

(((* a *) c (* f *)) g ((* d *) e (* b *)))

For each of the following statements, indicate the order in which the values of testTree will be displayed:

```  Part a. testEnumeration(new TreeEnumeration(testTree,
new StackVector()));

Part b. testEnumeration(new TreeEnumeration(testTree,
new QueueVector()));

Part c. testEnumeration(new TreeEnumeration(testTree,
new PriorityQueueVector(
new ObjectTreeComparator(
new StringComparator()))));

Part d. testEnumeration(new TreeEnumeration(testTree,
new PriorityQueueVector(
new ObjectTreeComparator(
new StringComparator().invert()))));```

Notes:

• new StringComparator() returns a comparator that compares Strings using alphabetical ordering. That is, if String s1 precedes String s2 in alphabetical ordering, then the comparator treats s1 as less than s2.
• If c is a comparator, then c.invert() returns a new comparator that inverts the sense of c. That is if c treats v1 as less than v2, c.invert() treats v2 as less than v1.
• new ObjectTreeComparator(cmp) takes a value comparator cmp and returns a comparator on ObjectTrees that compares ObjectTree t1 and ObjectTree t2 as follows:
• If t1 and t2 are both leaves, they are considered equal.
• If t1 is a leaf and t2 is not, then t1 is considered less than t2.
• If t2 is a leaf and t1 is not, then t1 is considered greater than t2.
• If neither t1 nor t2 are leaves, the ordering of t1 and t2 is determined by the ordering of cmp on the node value of t1 and the node value of t2. That is t1 is less than t2 if and only iff cmp determines that the value of t1 is less than the value of t2.

Submission Details: Turn in written answers for this problem. There is no softcopy submission for this problem.

## Problem 2: An Array Implementation of Integer Vectors

The IntVector class

We have seen that the Java Vector class is a versatile data structure handy for a wide range of uses. The fact that the elements of a vector have type Object means that vectors can store any kind of object. However, as we have seen, this feature is a source of inconvenience and inefficiency when the elements of a vector all have the same type. In this case, every extraction of a vector element requires a type cast, which not only makes the code uglier, but implies a run-time check on the type of the object. The situation is even worse in the case of storing primitive datatypes in a vector. In this case it is additionally necessary to package each primitive datum in an instance of a "wrapper class" (e.g. Integer, Boolean, etc.) before storing it in the vector, and unpackage it upon extraction.

In this problem, we will explore the implementation of an IntVector class that is a template for a specialized kind of vector that can store only integers. The IntVector has the same kinds of methods as Vector, except that wherever Vector returns an Object, an IntVector returns an int. When using the IntVector class to model a collection of integers, it is not necessary to package the integers into instances of the Integer class, nor is it necessary to use type casts when extracting elements from the vector.

We will implement an instance of IntVector using an array of integers. Here is a diagram of one instance of IntVector that contains, in order, the three integers 17, 0, and 42:

The elts instance variable points to an integer array that stores the elements of the vector. The number of slots in the array (known as the capacity of the vector) can be any number greater than or equal to the number of elements in the vector. The size instance variable indicates the number of slots (from left to right, starting at slot 0) that contain the elements of the vector. The remaining slots are extra space for the vector to "grow into". These extra slots may contain any integers whatsoever; their values do not matter because they are ignored by the IntVector methods. We shall refer to the values of these extra slots as "garbage". In the above example, the size of 3 indicates that only slots 0 through 2 hold vector elements and slots 3 and 4 hold garbage.

We will assume that as long as the number of elements in the vector remains less than or equal to the capacity, the array held by the elts variable does not change. In this case, vector operations that change, add, or remove elements must rearrange the elements within the slots of the exising array. For instance, performing v.addElement(-9) and then v.insertElementAt(230, 2) on the above vector representation should change the state of the objects as follows, where the fact that the array label has not changed indicates that it is the same array as in the previous diagram.

When an element is added or inserted into a vector whose size is equal to its capacity, it is necessary to increase its capacity. This is accomplished by creating a larger integer array, copying the vector elements from the old array to the new array, and making elts point to the new array. The number of slots by which the capacity should be increased is indicated by the capacityIncrement instance variable. For example, since the capacityIncrement is 4 in the example, performing v.addElement(111) installs a new integer array of size 5 + 4 = 9 in elts before it performs the insertion. The old array will be reclaimed by the Java garbage collector. By default, the garbage slots in the new array will initially contain 0, although after other vector operations the garbage slots might later contain any integer.

We will assume the convention used in Java's Vector class that if the capacityIncrement is 0, then the capacity of the vector should be doubled when the array needs to grow. For instance, if the capacityIncrement had been 0 above, then the new array would have had 2*5 = 10 slots.

The initial capacity and capacity increment of an IntVector instance are specified by arguments to the IntVector constructors:

Constructor Methods

```public Vector(int  initialCapacity, int  capacityIncrement)
public Vector(int  capacityIncrement)
public Vector()```

An invocation of the first constructor creates an integer vector with no elements (i.e., size is 0) whose initial capacity is initialCapacity and whose capacity increment is capacityIncrement. In the other constructor methods; the parameters not supplied are assumed to be 0.

The IntVector class supports the following subset of the instance methods supported by Java's Vector class. If you have questions about the behavior of a particular method, consult the on-line JDK 1.0.2 API, accessible from the CS230 Documentation page. The Vector class is in the java.util package. (Of course, the following specifications differ from those in the Vector class by replacing every Object type by the int type.)

Instance Methods

```public void addElement(int elt);
public int capacity();
public int elementAt(int  index);
public void ensureCapacity(int  minCapacity);
public final int indexOf(int elt)
public void insertElementAt(int elt, int  index);
public void removeAllElements();
public boolean removeElement(int elt);
public void removeElementAt(int  index);
public void setElementAt(int elt, int  index);
public int size();```

Implementing the IntVector class

Part a.

In this problem, you will implement the IntVector class using the representation discussed above. The code that you need is in the IntVector folder within the ps7-programs folder. You should flesh out the skeletons of the above constructor methods and instance methods in the IntVector.java file. The IntVectorTest.html applet tests your implementation on a suite of test cases. Each test case will be run on vectors whose capacity increments are 0, 1, and 8.

Note that the solutions to the array implementation of the Hand abstraction in Problem Set 2 may be worth reviewing as part of doing this part.

Part b.

The IntVector folder has another testing applet, IntVectorTimingTest.html, which contains the following testing methods:

```	public void addTest (int capacityIncrement, int size) {
IntVector v = new IntVector(capacityIncrement);
for (int i = 0; i < size; i++) {
}
}

public void insertTest(int capacityIncrement, int size) {
IntVector v = new IntVector(capacityIncrement);
for (int i = 0; i < size; i++) {
v.insertElementAt(i,0);
}
}```

For each of the above testing methods, and for each capacity increment in the set {0, 1, 8}, analyze the running time of the testing method as a function of the size argument based on your knowledge of how the IntVector class is implemented. Since there are two methods and three different increments, you should give six different analyses. Each analysis should include (1) a recurrence equation characterizing the running time for the test method as a function of size; and (2) a solution to the recurrence equation expressed in theta notation. You do not have to give an exact solution to the recurrence equation.

Part c.

In this part, you should execute the testing applet, IntVectorTimingTest.html, which executes the test methods described in part b on various parameters, and prints how much time (in milliseconds) each testing method takes. Based on the numbers that are printed out, characterize (using theta notation) the running time of the two testing methods for each capacity increment in the set {0, 1, 8}. Since there are two methods and three different increments, you should give six different characterizations. Do these empirical characterizations match the answers you developed in part b? Try to explain any discrepancies you observe between your answers to this part and your answers to part b.

Submission Details: For your softcopy submission, turn in the final version of the IntVector folder that includes your final version of IntVector.java. For your hardcopy submission, turn in the following:

• IntVector.java
• a copy of the transcript of the test cases. You can save the results of the IntVectorTest test cases (which are in the stdout window) to a file by clicking on the apple pull-down menu in the upper left corner and selecting Java Runtime. In the resulting menu, select Save To Text File and specify the desired output file name.

## Problem 3: Implementing Bags as Unsorted Immutable Lists with Duplicates

In this problem you will implement the Bag abstract data type presented in class as an unsorted immutable list with duplicates. An instance in this implementation will have two instance variables:

1. An instance variable elts that contains an immutable list of bag elements. Inserting an object into the bag should be accomplished by storing into elts the result of prepending the object to the list.
2. An instance variable comp that contains the comparator used for testing equality of objects in this bag.

For example, consider the following sequence of statements:

```Bag a = new BagUnsortedImmutableListWithDups(new StringComparator());
a.insert("d");
a.insert("a");
a.insert("b");
a.insert("d");
a.insert("c");
a.insert("b");
a.insert("a");
a.insert("b");```

After this sequence of statements, the variable a should contain a pointer to an instance of the class BagUnsortedListDups having the following structure:

In this problem, you will implement bag in terms of the concrete representation sketched above. You should implement the following bag operations by fleshing out the skeletons in the file BagUnsortedListDups.java in the Object Collections folder of the ps7-programs folder.

Constructor Method:

`public BagUnsortedListDups (Comparator c);`

Instance Methods:

```// You must implement all of the following

// From the Collection Interface
public void insert (Object x);
public int size();
public boolean isEmpty();
public void clear();
public Object clone();
public ObjectList toList();

// From the EqualityCollection Interface
public Object delete (Object x);
public boolean isMember (Object x);
public void deleteAll();

// From the UnorderedCollection Interface
public Object choose();
public Object deleteOne();

// From the Bag Interface
public int occurrences(Object x);
public int count();

// These have already been implemented for you

// From the Collection Interface
public Object first();
public Object deleteFirst();
public Enumeration elements();
public String name();
public String toString();

// From the EqualityCollection Interface
public void union (Collection c);
public void intersection (Collection c);
public void difference (Collection c);
public Comparator comparator ();```

Notes:

• You can test your implementation by double-clicking on BagUnsortedListDups when running the CollectionsTest.html applet.
• The BagUnsortedListDups.java file includes local abbreviations for the ObjectList operations. So you can use head(...) instead of ObjectList.head(...), etc.
• Be sure to use the comparator comp to test for equality between objects. That is, do not use .equals() or == to test for equality between objects. Refer to the Comparator contract handed out in class for how to use instances of the Comparator class.
• Write any auxiliary methods you find helpful.
• The methods choose() and deleteOne() should throw a CollectionException if the bag is empty.
• The deletion methods delete(Object x) and deleteAll(Object x) should not throw any exception if x is not in the bag. The interface says that such operations are not errors.
• Because the bag abstraction does not specify any order on its elements and because the representation uses an unsorted list, none of your operations needs to maintain the relative order of elements. This means it is OK to have iterative implementations of the bag operations that change the order of elements in the list.

Submission Details: For your softcopy submission, turn in BagUnsortedListDups.java.For your hardcopy submission, turn in BagUnsortedListDups.java and a copy of the transcript of the test cases. You can save the results of the CollectionTest test cases by following the steps specified in Problem 2. 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 4: Implementing Bags as Vectors of Sorted Entries

In this problem you will implement a very different representation of the Bag ADT than the one used in Problem 3. Here, an instance representing a bag will have two instance variables:

1. An instance variable elts that contains a vector of BagEntries, where each BagEntry keeps track of an element and the number of times it appears in the bag. The vector should be sorted from low to high by the element of the BagEntries.
2. An instance variable comp that contains the comparator used for testing equality of objects in this bag.

For example, consider the following sequence of statements.

```Bag b = new BagVectorEntriesSorted(new StringComparator());
b.insert("d");
b.insert("a");
b.insert("b");
b.insert("d");
b.insert("c");
b.insert("b");
b.insert("a");
b.insert("b");```

After executing the above sequence, the variable b should contain a pointer to an instance of the BagVectorEntriesSorted class with the following structure:

As suggested by the diagram, each BagEntry instance has two instance variables: an Object elt that holds the element and an integer num that holds the number of occurrences. You may assume that these instance variables are public. This means that if be is a bag entry, you can extract its elt part via be.elt and its num part via be.num.

Your implementation should maintain the following invariants:

• Each element in the bag should appear in exactly one BagEntry.
• Each num should be positive. If the number of occurrences of an element in the bag is reduced to zero (say, by deleting the element), then the BagEntry must be removed. For example, if b is the bag depicted in the above picture, then b.delete("c") would result in the following diagram:

In this problem, you will implement bag in terms of the sorted BagEntry vector representation sketched above. You should implement the following bag operations by fleshing out the skeletons in the file BagVectorEntriesSorted.java in the Object Collections folder of the ps7-programs folder.

Constructor Method:

`public BagVectorEntriesSorted (Comparator c);`

Instance Methods:

```// You must implement all of the following

// From the Collection Interface
public void insert (Object x);
public int size();
public boolean isEmpty();
public void clear();
public Object clone();
public ObjectList toList();

// From the EqualityCollection Interface
public Object delete (Object x);
public boolean isMember (Object x);
public void deleteAll();

// From the UnorderedCollection Interface
public Object choose();
public Object deleteOne();

// From the Bag Interface
public int occurrences(Object x);
public int count();

// These have already been implemented for you

// From the Collection Interface
public Object first();
public Object deleteFirst();
public Enumeration elements();
public String name();
public String toString();

// From the EqualityCollection Interface
public void union (Collection c);
public void intersection (Collection c);
public void difference (Collection c);
public Comparator comparator ();```

Notes:

• You can test your implementation by double-clicking on BagVectorEntriesSorted when running the CollectionsTest.html applet.
• The BagEntry class has already been implemented for you. Given an element e and a number n, you create a new BagEntry via new BagEntry(e,n). The elt and num instance variables of BagEntry are public, so if be is an instance of BagEntry, be.elt extracts the elt instance variable and be.num extracts the num instance variable.
• Don't forget to use a (BagEntry) cast when extracting entries out of the elts vector.
• Be sure to use the comparator comp to test for equality between objects. That is, do not use .equals() or == to test for equality between objects. Refer to the Comparator contract handed out in class for how to use instances of the Comparator class.
• Write any auxiliary methods you find helpful. In particular, it is highly recommended that you write one or more auxiliary methods for finding entries and the index of entries in a sorted vector of entries. Otherwise, many of your methods will contain similar code for accomplishing this task. It is a particularly good idea to define an auxiliary method for finding a given Object x in a vector of bag entries that returns the following three pieces of information:
1. The BagEntry in the vector whose elt is x, or null if there is none.
2. The index of the BagEntry containing x, or, if there is no such entry, the index at which an entry containing x would be inserted.
3. A boolean indicating whether x appears in an entry of the vector.
• The methods choose() and deleteOne() should throw a CollectionException if the bag is empty.
• The deletion methods delete(Object x) and deleteAll(Object x) should not throw any exception if x is not in the bag. The interface says that such operations are not errors.
• Be careful to distinguish size() from elts.size() in your code. Failure to do this can lead to subtle bugs.
• The BagVectorEntriesSorted.java file includes local abbreviations for the ObjectList operations. So you can use head(...) instead of ObjectList.head(...), etc.

Submission Details: For your softcopy submission, turn in BagVectorEntriesSorted.java.For your hardcopy submission, turn in BagVectorEntriesSorted.java and a copy of the transcript of the test cases. You can save the results of the CollectionTest test cases by following the steps specified in Problem 2. 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).