CS 112 B1 - Spring 2003: Homework 7
Due Thursday, May 1 at 11:59 P.M.
Please keep in mind the policy on collaboration, as described on the syllabus.
Your code will be graded for style as well as correctness
and should conform to the following style guidelines.
PROBLEM 1:
(30 points)
Here is (most of) the code for a hash table, with integer data keyed
by strings, and a main to test it. This is an exercise in a lot
of code reading a little bit of code writing. Add the Find, Remove and
GiveStats methods to the class HashTable, and test them using main.
GiveStats should compute the total number of elements in the table
as well as the average time required to search for an element that is
known to be in the table. The latter is computed by adding
the linked list positions of all the elements and dividing by the
total number of elements (for example, in a table with 1 element,
the average will be 1; in a table with two elements, the average will
be 1 or 1.5).
PROBLEM 2:
(10 points)
Find a set of distinct keys that will always hash to the same
location (no matter what the table size), thus resulting in poor
performance for the average seek. Submit a file named
example.txt
that has 9 lines, with one string per line, such that no matter
what the table size, all the keys will hash to the same location,
resulting in the average seek time of 5. The nine strings must be distinct.
PROBLEM 3:
(10 points)
Modify the hash function in the class HashTable
so that every letter of the key is taken into account, and the bad example
is no longer bad.
Submit: htable.cpp and example.txt
only, in directory hw7.
You should not have to modify other files, and hence should not submit them.