CSC 241- Lab 5 (Due May 2nd 1997)

Theme ...

There are three main objectives that this lab helps us meet:

• You need to learn about two very important data structures: Hash Tables and Binary Search Trees. So, we will cover them here.
• experimentation is our most effective tool for determining time and space complexity for various algorithms and data structures. You will learn some valuable techniques.
• Last, but not least, you will gain more experience in practical usages of class hierarchy in Object Oriented design. More specifically, you will learn about interfaces in Java.

In lab3, we learned about creating abstract classes and extending them in different ways and providing distinct implementations. We also learned about building generic stacks and queues that held any subclass of Object. In this lab, you will be introduced to the concept of interfaces that are pure design tools in Java. Interfaces only allow for identifying methods and constants, no implementation, thus, they are very similar to abstract classes. They do, however, provide further flexibility in design than a simple class hierarchy which I hope to show here.

I have developed an interface named Keyed that you will use. This interface can be implemented by all classes that we wish for their objects to be identified uniquely through a key value. This characteristic is important when dealing with ordered collections, we need to be able to distinguish and compare our objects that we keep in such a collection. Also, for us, it means that we won't have to just build a class for a binary search tree that holds integers, we will build one that holds any keyed object.

We will also work with an interface named orderedCollection that allow us to maintain uniquely keyed objects. I have designed a Binary Search Tree class and a Hash Table class that implement Ordered Collection. They both need their update methods implemented which you will do in this lab. I hope that you will understand why the concept of keyed is important in these Collections. Binary Search Trees and Hash Tables differ from stacks and queues in that they care about uniqueness of elements that they hold, in neither case, can we allow duplicates. Making sure that all objects held in ordered collections adhere to the Keyed interface enable us to ensure uniqueness.

Once, you finish building these ordered collections, we can compare their behavior for adding, removing, and finding values. You will also learn to do some performance tunning. There are many variations to hash tables, so, our results won't be complete, but, I think, you will learn something!

Create directories and copy some files

1. cd public-html/classes/csc241
2. cp -r ~mohammad/public-html/classes/csc241/Collection/ . -- don't forget the dot or the -r.
3. From public-html/classes/csc241 directory, type ls -R List. The list should look like:
   

       Collection/:
       Keyed.class               hashNode.class            orderedCollection.class
       Keyed.java                hashNode.java             orderedCollection.java
       Tree.class                hashTable.class           testCollection
       Tree.java                 hashTable.java            treeNode.class
       duplicateException.class  notFoundException.class   treeNode.java
       duplicateException.java   notFoundException.java
   
       Collection/testCollection:
       test1.class      test2.class      testKeyed.class
       test1.java       test2.java       testKeyed.java
             

   
   

Compile all Java files and run the test program

1. Use javac *.java in each directory to compile all of the above .java files.
2. Run the program that tests the two implementation of orderedCollection.
   • You need to be in the directory public-html/classes/csc241/Collection/testCollection.
   • Execute test1 with java test1 tree and java test1 hash 10
   • Execute test2 with java test2 tree and java test2 hash 10

Implement the update method

I have left the implementation of the update method in Tree and hashTable for you. In each case, you must use the key from the parameter x to locate the object in the collection and replace your finding with the new version. In the tree version, write update in a similar way as I have done remove and add by using find to look for the element being updated. If element is found in collection, using an internal method written similarly to insert and del locate and replace the element in the Tree.

Modify test2.java to test your update methods.

Experiment and Tune

We like to compare the performance of our two implementations of orderedCollection. To effectively compare performances for hash tables and binary search trees you need a bigger pool of data. Just inserting 100 or so elements and performing 100 or so operations on the collections will not give you a definitive conclusion on their performance. We also know that the tree version performs a find every time add, remove or update are called, this doubles the traversal time for any successful tree operations. Here are the things that you need to do and the questions that you must answer.

• Modify test2.java program to test for inserting 10,000 elements and performing 1,000 random operations. Two things:
  1. The method rand that I wrote in this test program is called with 10 and 110 when needing a random number. Given how many elements you like to insert into a collection, what is a better range of values for what you would attempt to add, remove, etc? Modify the test program accordingly.
  2. At this point, we should be able to trust our operations, so we should not need to print any echos for what operation is being performed or if it was successful or not. performing output, in general, gets in the way of performance comparisons. So, don't perform dump at all. You shouldn't do any print or println anywhere in the test program, except for outputting the time it took to run at the bottom.
  
  
• Run the test program for tree and hash. Answer the following questions:
  1. What times are printed when you run the test program?
  2. What happens if you use a size argument that is larger than 10 when testing the hash version? At what size does the hash version begin to out perform the tree version, if ever? Be sure to indicate in your email, how many times you ran the program, with what arguments, and what your results were clearly.
  
  
• Modify Tree.java so that the find method is not used in add, remove, or in your update. This means that insert, del or the helper method you wrote for update should be redesigned to throw the appropriate exceptions. For example, insert, after testing for null root, must test to make sure the key of the element being inserted is not at root, if it is, it must throw the duplicateException.

  What are the answers to the questions above when this version of Tree is used?