CMSC 420 Section 0401 - Programming Assignment 1

Overview:

Hashing is very simple to implement, but difficult to analyze. Unlike other data structures, experimental analysis using programs seem to be one of the good ways to understand hashing better, and believe in the theoretical prediction.

The broad goal of this assignment is to verify how well double hashing works. You will later integrate this assignment in a broader assignment, programming assignment 2, that deals with interaction of light and (possibly) visibility that will test your understanding of hierarchical data structures such as quadtrees.

Part A: Double Hashing (Due Feb. 21, 8:00AM)

You will write then class HashTable which extends provided AbstractHashTable. The collisions is handled by open addressing with double hashing. You will store items as (key, value) pairs in the hashtable using a hash code function discussed in the class. The mapping of the hash code function value to legal array indices will be performed using the MAD method. You will resolve collisions using double hashing. We provide test drivers to output the cost of the operations insert(put), search(containsKey), delete(remove). The detailed specification is here.

Part B: Visualization (Due Mar. 8, 11:45PM)

The purpose of this part to try and see if the theoretical values we derived matches the experimental values you will obtain.

The goal is to output gnuplot files comparing your answers with the theoretically predicted value.

The detailed specification is here.

Part C: Brent Variation on Double Hashing (Due Mar 22)

Does the Brent method help? Implement the Brent variation on double hashing. For this part, assume load factor = 1, fully loaded.

Part D: Gonnet-Munro Variation on Double Hashing (Due April 14)

Does Gonnet-Munro help? Implement the Gonnet-Munro scheme. For this part, assume that load factor = 1, fully loaded.

Grading:

Submission:

Submission will be handled using the submit program: "~sc42002/bin/submit [index] [file]" under your class account.