Description
Hashing (30 points)
Implement quadratic probing and then run tests on the number of probes required at
various load factors to obtain a graph like the one shown in Figure 5.12.
For this assignment, results and analysis are particularly important. You’re not just
programming; you’re experimenting with a program and reporting on the results of those
experiments.
To keep things simple, you may assume that items to be stored are integers and that
there will never be more than 1,000 of them stored at any one time. Do not rehash.
Maps and Hashing (70 points)
(a) Implement the most efficient version of the “word puzzle” algorithm of section
(the one shown in Figure 4.72) using the STL map. Use the exact implementation
provided with the book. Your executable should run as follows:
./testMaps
where
1. Compute and print out the time it takes for the computation of the adjacent
words.
2. Prompt the user to provide a word, and then print out all its adjacent words.
Print out also the time it took for searching for that word.
(b) For this part of the assignment DO NOT use the STL map. Create your own
templated hash-map class that only supports lookup (find), insert and delete (you
can use lazy deletions) operations. You should also provide an operation that
visits all the elements in the hash-map (in the way they are stored in the hash
table). The hash-map (use quadratic probing) will store a key with an associated
value. Note that you need to provide a good hash function for strings. You don’t
have to implement iterators for your hash-map implementation. Now using your
own hash-map implementation, implement the most efficient version of the “word
puzzle” algorithm. Your executable should run as follows:
./testMyHashMap
The first argument is the list of words (dictionary) and the second argument an
integer that specifies the initial size of the hash table.
Provide the tests (1) and (2) as in part (a). Experiment with different initial sizes
(from very small, i.e. 51 to larger) and measure the change in running time.
