CMSC 420 Section 0401 - Programming Assignment 1, Part B

CMSC 420 Section 0401 - Programming Assignment 1, Part B
Due March 8, 11:45PM

Part B - Visualization with gnuplot

In part B, you will extend the work you did in part A.

You need to update your implementation of HashTable.java.
You also need to provide a driver class HashTablePlotData.java, which will generate gnuplot data.
See description as follows:

Recall that in part A, you wrote HashTable.java. In part B, the class extends AbstractHashTable as shown below:

public class HashTable extends AbstractHashTable {
	// Methods with the same functions as in Part A
	public HashTable (int tableSize);
	private HashTable ();
	public int getSize ();

	// In Part B, hashValue(String key) and probleHashValue(String key)
	// are inherited from AbstractHashTable.
	public int hashValue (String key);
	public int probeHashValue (String key);

	public int probeCount; // doesn't need to declare, inherited from AbstractHashTable.
	public boolean put (String key, Object value);
	public boolean containsKey (String key);
	public boolean remove (String key);

	// Methods new in Part B
	public Object get (String key);
	public int longestProbe ();
    }

If you note carefully, you will find that in Part B, two new methods are defined:

public Object get (String key): Return the element corresponding to key , or null if the key is not in the table.
[3/6/02 added by TA:] For full credits, you need to increase probeCount by 1 for each probe in get, as what you did for put, containsKey and remove in part A.
public int longestProbe (): Return the length of the longest successful probe sequence. In addition to the time/cost for successful and unsuccessful search, this quantity is yet another measure of the quality of the hashing scheme. For full credits, you cannot brute-force search the whole table to implement this method. You need to update the length of the longest successful probe sequence whenever method put(String key) or remove(String key) are called. And your longestProbe() takes O(1) constant time. You may need an array for updating the length of longest probe.
For the purpose of grading, the methods hashValue(String key) and probeHashValue(String key) are no longer abstract in AbstractHashTable.java. Likewise, setHashArgument(int a) and setMADArguments(int a, int b) are gone in Part B.
All other methods have the semantics as in part A.

Next the driver. The driver class HashTablePlotData will output a gnuplot file which in turn will generate a PostScript file like success.ps, unsuccess.ps, and longest.ps. (Take a look at these files now! More on this gnuplot business follows, but basically most of the spade-work has already been done. You can concentrate on the programming.) The goal is to produce charts of average cost(probes) of successful and unsuccessful search with collisions handled by double hashing. How do we produce these files?

Your program will be executed as "java HashTablePlotData putfile [findfile] ", where putfile and findfile are text files containing items (keys and elements).
For successful search, the input is only putfile without findfile. The putfile contains key-value pairs (i.e., items with keys and elements) to be inserted in the table. Each line in this file contains the a key and its mapped element (values are separated by spaces in our sample input. You may assume the leading character of each line is not a space.) For full credit, search cost of duplicate keys should not be counted in average search cost.
For unsuccessful search, the input has findfile in addition to putfile. The findfile, with the same format as putfile, containing items that are not found if you invoke the containsKey() method. These items are for calculating the average cost of (experimental) unsuccessful search. For full credit, you must exclude items with keys present in putfile for "unsuccessful search".

findfile

Your driver can figure out whether the intention is to produce a "successful" or "unsuccessful" plot file based on the number of arguments on the command line.
The output, consisting of multiple data records, is printed to the standard output stream (System.out in Java). Each line contains a record corresponding to a load factor. The requested table capacity is the number of distinct keys in putfile. Note that the real table capacity is a prime as in Part A.
For successful search, each record has four fields separated by spaces in sequence:
(1) number of items in the table,
(2) load factor,
(3) average successful search cost of double hashing, and
(4) length of longest successful probe sequence.
For unsuccessful search, each record has three fields in sequence:
(1) number of items in the table,
(2) load factor, and
(3) average (experimental) unsuccessful search cost of double hashing.
The fields are also separated by spaces.

Use HashTable.probeCount wisely to implement HashTablePlotData. That basically finishes your programming task. Here is some post processing. Visualization is accomplished with gnuplot. You can figure out how this works by the examples provided below.

The driver is run using "java HashTablePlotData put53 > plot53s" with putfile put53. Here 53 means the number of items in the putfile.
The type of output we are looking for is here: plot53s.
Using the shell command "gnuplot plotps1" with the script file plotps1, you get the file success.ps.
Here is, finally, one the files we actually want success.ps.
Likewise, you may get the chart of average unsuccessful search cost unsuccess.ps by the 2 steps:
(1) "java HashTablePlotData put53 find30 > plot53u" to get plot53uwith files put53 and find30
(2) "gnuplot plotps2" with the script file plotps2.
Moreover, "gnuplot plotps3" with plotps3 to get the chart of length of longest successful search probe sequence longest.ps.

plot53s

[3/4/02 added by TA:] If you use gnuplot version 3.5 or before, you need to do a slight modification of the script files. Replace the line "set data style lp" by "set data style lines".
[3/5/02 added by TA:] You may assume the putfile always with name putxxx, where xxx is the number of (possibly duplicate) keys in the file. Similarly, you may also assume the findfile always with name findxxx with the same naming convention.

Grading:

The maximum points of part B is 100.
Grading will focus on the 2 new methods of HashTable and the class HashTablePlotData. However, bugs in Part A may break the functionality required in this part.
The public drivers for grading will be posted soon.
[3/1/02 added by TA:] Public driver HashTableDriver1.java is now available with correct output.
[3/5/02 added by TA:] Get your successful search plot data myplot53s by "java HashTablePlotData put53 > myplot53s" with put53. Try "java ColumnCompare plot53s myplot53s 5 5 10 5" with ColumnCompare.java to see your scores. Max points are 25.
[3/5/02 added by TA:] Get your unsuccessful search plot data myplot53u by "java HashTablePlotData put53 find30 > myplot53u" with put53 and find30. Try "java ColumnCompare plot53u myplot53u 0 0 10" with ColumnCompare.java to see your scores. Max points are 10.
[3/18/02 added by TA:] This is the all grading drivers: p1b_drivers.tar.gz.

Submission:

Tar and gzip your *.java files, and submit.
Submission is handled using the submit program with submission index 2. Ex: "~sc42002/bin/submit 2 foo.tar.gz".
I(TA) reserve the right to deduct up to 10 points if you don't follow the submission procedure.

Web Accessibility