CS230 Data Structures, Wellesley College, Fall 1999

Problem Set 7

Due any time Friday, November 12

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


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:

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++) {
			v.addElement(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:


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:

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:

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:

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).