Download the class LinkedSetOutline.java from Moodle, and rename it LinkedSet1.java.
(a) Implement the methods of this class. To implement the equals, containsAll, addAll, removeAll and retainAll methods you should assume that the second set that has an implementation for which the iterator returned by the iterator method visits elements in ascending order. You may not assume anything else about the implementation of that (i.e. that it is an ArraySet, or a LinkedSet for example). You should ensure that the complexities of your operations are as stated in the comments included for each method.
You will need to write yourself a testing program to ensure that your methods work correctly. You will not be asked to submit this program (your classes will be tested against my own test program). There is an example test program on Moodle that you can modify.
(b) Copy your LinkedSet1.java into a new class LinkedSet2.java. Reimplement the equals, containsAll, addAll, removeAll and retainAll methods -- this time making no assumption about the set that at all (except that its iterators hasNext and next methods are constant time operations). I.e. you should not assume that the associated iterator visits elements in ascending order. In each case you should amend the comments for each method to indicate the new complexity, and include an explanation justifying this complexity.
This exercise is an experiment in hash tables. You are to explore the effects of different hashing functions, effects of loading factor (capacity of the table), and two parameters: scaling factor and shift. You will submit a table of results including a note on your observations (see the file results.txt).
You should:
- Download files dictionary.txt, GeneralHashFunctionLibrary.java, HashException.java, HashTable.java, results.txt and Test.java
- In HashTable.java implement the method String stats(){...}
- Using the dictionary.txt data set perform experiments by varying the parameters N, scalingFactor and shift, and by changing the method hashCode(String s)in HashTable.java (by cutting and pasting hashcode methods from Arash Partow's "General Purpose Hash Function Algorithms Library" (GeneralHashFunctionLibrary.java).)
- enter your results into the file results.txt. You should create a table for each different combination of N, scalingFactor and shift. Note that in the file results.txt provided, one table template is included. In this case all of the hashcodes are considered. You must decide how many tables to use and how many hashcodes in each case you require.
You could modify the program Test.java so that it is easier to perform your experiments. In fact, maybe write your own program Experiment.java.