Print out the total number of collisions that happen if you are inserting random elements between 0 and 999 into the hash tables that use the three different methods of collision resolution. Specifically, you need to compute the average number of collisions per inserted element if the table is (approximately) 1/4 full, 1/2 full, 3/4 full, and completely full. Note that the quadratic probing uses a table of 64 elements, and the other two tables have 67 elements.
The results for number of collisions should be printed to a file
statistics.txt.
Please submit your test program and the file with the results.
We assume that objects sorted by the algorithm implement the following
abstract class KeyOneTwenty:
public abstract class KeyOneTwenty {
// public method that returns a key only if
// it's between 1 and 20
public final int Key() {
int key = _Key();
if (key < 1 || key > 20) {
System.out.println("invalid key " + key);
System.exit(0);
}
return key;
}
// private class-specific method
protected abstract int _Key();
}
public static void countingSort(KeyOneTwenty [] items)
StringKey which extends
KeyOneTwenty. The class has one private variable
str of type String. The _Key() method of the
class should return the length of the string.
Test your counting sort algorithm by creating an array of StringKeys in main and calling the method countingSort on that array.
InvalidKeyValueException which is an
extension of Exception (not
RuntimeException!).
KeyOneTwenty so that the Key method
throws the InvalidKeyValueException when the key is
invalid (instead of exiting the program via System.exit(0)). No error
message should be printed.
Check your program to make sure that only the
InvalidKeyValueException is caught. The rest of the
exceptions should behave as usual (i.e. print the error message and
terminate the program).
Submit all of your test cases.
More specifically, you need to do the following:
You should start by commenting out the old method code, put some dummy return values for all non-void methods, such as an empty string for toString(), and make sure that the program compiles and runs. Then start writing code for the methods one by one, compile and test often.
currentTimeMillis() of the System class
returns the current time in milliseconds (as a long integer). Get the
reading of the time before and after a call to BFS() and DFS(),
subtract the readings, and print out the results. For instance, to
find out how long a BFS() method takes, we can write this:
long time1 = System.currentTimeMillis();
g.BFS();
long time2 = System.currentTimeMillis();
System.out.println("The method took " + (time2 - time1) + " milliseconds");