You will learn ...
In this lab, you will work with the Set Package. I developed two interfaces that you need to become familiar with. I have already implemented the Set interface with a Tree class and a hashTable class. This interface represents collection classes that hold unique objects.
The elementType interface needs to be implemented by any class where its objects are going to be stored in our in a set. Such objects in adhering to the elementType interface must provide a key method that uniquely identify them. This characteristic is important when dealing with sets, we need to be able to distinguish and compare our objects that we store in them. With the ability identify elements uniquely and compare them, we are enabled to store them in a way where we can find them quickly.
In completing this lab, You will also build an on-line dictionary application that will utilize our tree or hashTable class. Building this application will require you to implement elementType in a class that will hold a word/meaning.
cd public-html/classes/csc241
cp -r ~mohammad/public-html/classes/csc241/Set/ . -- don't forget the dot or the -r.
ls -R Set. The list should look like:
Set: Set.java duplicateException.java hashNode.java notFoundException.java treeNode.java Tree.java elementType.java hashTable.java testSet Set/testSet: elementForTest.java test1.java lab5.dat test2.java
java test1 tree and
java test1 hash 10
java test2 tree and
java test2 hash 10
First lets perform a few experiments to compare performances for hash tables and binary search trees. We need a bigger pool of data than what test1 and test2 use to test these data structures with; just inserting 100 or so elements and performing 100 or so update operations on these structures will not give you a definitive conclusion on their performance.
Modify the test2.java program to test for inserting 10,000 elements and 1,000 randomly chosen update operations after the insertion are complete. Two thing that you should not over look:
Run the test program with tree as its argument to test the tree version and collect the elapsed time for 5 runs and record their average.
Run the test program with hash as its argument and the size 10 again collecting the elapsed times for 5 runs and recording their average.
What happens if you use a size argument that is larger than just 10 when testing the hash version? Is there a point where hashtable performs better than BST. When testing for higher hash table sizes, be sure to average the results of 5 runs in each case before recording them.
In response to the questions in this part, in your email, include:
In this section, you will modify some of the code for both data structures and again through experimentation respond to a performance question.
The way things work now, the actual process of inserting or deleting elements don't have to bother with the possibility of either the element not being there, when it should be, or it being there, when it shouldn't be. The idea here is simple, by using find, you traverse the data structure looking for the element; in remove, if it is not there, we throw an exception; in add, we do the opposite, if it is there, we throw an exception. This way, the rest of these methods don't have to deal with exceptions.
Remove the calls to the find method. Throw no exception in the add or remove methods of the Tree class. The insert and del methods in the Tree version need to be modified to account for their respective exceptions. Both insert and del need a throws with the appropriate exception that they should now throw in their method header. In insert you must consider that the element may already be in the tree and if it is, throw the duplicateException. In del you must consider that the element might not be in the tree and if it is not, throw the notFoundException. add and remove methods still need their "throws ..." clause in their header. Also, no try/catch is necessary since the respective calls to insert and del methods could cause exceptions to be thrown, add/remove will implicitly throw the needed exceptions.
hashTable need to updated in a similar way. the difference is that add and remove don't call any recursive methods, thus, they themselves have to be changed to find the elements.
test changes that you make with test2 (i.e. with output), to make sure these methods still work correctly.
Once you know they work correctly, you need to repeat the analysis that you performed in the previous section in order to respond to the following question:
Can the performance of either Tree or hashTable be improved by making the changes specified here.
Submit the code for both Tree and hashTable with the modifications.
Build a dictionary application program. Your dictionary program needs to load word/meanings from a file and provide users with the following options:
You should have already copied a file into your testSet named lab5.dat. This file contains words and meanings in a simple format. This is the data file that you will use to initially load words and meanings.
Before developing the application program, you will need to first develop a dictionaryEntry class that implements elementType. This class must have two fields: word and meaning. It needs to provide the appropriate methods required by the elementType interface. The key method must return the word. The stringView must return a string that follows this template: The word is:XXXXXX with the meaning:XXXXXXXX Write a simple, but meaningful constructor for this class.
Then, write the dictionary application program that uses
dictionaryEntry to store word/meanings loaded from the input
file in a hashTable or a Tree.
Since, the data file has words that are already sorted, the tree
version will not work optimally, do you know why?
Your application should follow the algorithm given below:
Submit a copy of this application program, as well as, your dictionaryEntry class.
Add an additional option to the on-line dictionary built as part of lab5. This option enables the user to either see all words/meanings or a partial set of them.
The user needs to be prompted for a partial word/*. Lets assume the user response is stored in w. If w is a "*", all word/meanings are displayed, otherwise, the subset of the elements that match the content of w at their beginning are displayed. For example, if w is "la", all words in the dictionary that start with the substring la are displayed. Keep in mind that the toArray returns all elements from the set in an array, so you can use it to return all word/meanings and selectively display what you need.