Assigned |
|
Due |
|
Note |
Questions and a sample output will be posted shortly |
Updates |
09 April
The non-templated code has been moved into two new files in Mr. Frey's public directory -- Prime.C which contains isPrime() and nextPrime() and HashFuncs.C which contains the two hash functions. Prime.H and HashFuncs.H have also been created. Be sure to compile and link these new .C files and include them in your makefile. |
Updates |
12 April
|
Correction |
14 April |
Updates |
14 April |
The purpose of this project is to give you some exposure to Hash Tables (HT) and to experimentally study the time performance of hash tables, in comparison with that of binary search trees (BST). As discussed in the class, a randomly generated BST of n nodes takes on average of O(n log n) time to build; the height of such a BST is O(log n), which leads to a O(log n) average time performance for find and insert operations. On the other hand, find and insert operations for HT have O(1) time performance, provided the table is sufficiently large and a proper hashing function is used. In this project, you will verify these theoretical results through a sequence of experiments with BST and HTs using closed hashing and quadratic probing.
In this project, you will first construct a BST and several
HT's of different size by inserting the same sequence of randomly generated
integers, and then conduct both successful and failed find operations
over these data structures. You will collect statistics related to the
performance of both BST and HT during these operations and report your
findings. Below are the specifics.
Data Preparation
For a fair comparison, the same set of integers will be used to construct the
BST and HT's, and the same sequence of keys will be used for the find
operations in both BST and HTs. For this purpose, you are asked to build two
vectors of randomly generated integers v1 and v2. Both vectors
are of size N (the value of N will be provided as the second of the two command
line parameters. Integers in v1 will be used for constructing BST and
HT's; those in v2 are used for find operations. These two vectors
are constructed as follows:
Approximately half of integers in v2 are also in v1,
and another half are not, and consequent approximately half of your find
operations will succeed, and another half will fail.
BST
When doing the tree construction and find(x) operations, you need to
collect the number of comparisons for each operation. To be comparable to
probings in HT, the comparison here means how many objects are compared with x
in insert and find, NOT the number of actual comparison operators (=, <, >)
executed. For example, inserting an integer into an empty tree has 1 comparison
(comparing with null), a successful find with x = 4 on a path 1 -> 2
-> 3 ->4 -> 5 has 4 comparisons, and a failed find with x = 6
along the same path would have 6 comparisons (the 5 nodes plus the null).
Hash Tables
You will be experimenting with closed hashing, using the division method for
hashing and quadratic probing for resolving collisions as specified below:
h'(K) = K mod M
h(K, I) = (h'(K) + I2) mod M
HT's of different sizes, reflecting different load factors
"lambda", will be experimented. For a given N and lambda, the HT size
will be the smallest prime number greater than N/lambda. To observe the
influence of lambda on the HT performance, you are asked to run your program
with lambda = 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 for a given N.
Note: there is a small probability that, when quadratic probing is used, you
may not be able to find a empty cell for insertion even though the table is not
full. If this happens, record it and then proceed to insert the next integer
from v2.
Experiments
The procedure for the experiments is outlined below.
When constructing BST and HTs, the order of integers from v1
inserted shall be
v1[0], v1[1],..., v1[N-1].
Statistics needed for the final report should be collected throughout the
experiments. What data should be included in the final report are given next.
Reporting
At the end of the experiment, report the following in a well formatted output.
/afs/umbc.edu/users/y/p/ypeng/pub/CMSC341/Proj4/341-Spring04-p4_questions.txt
These questions are worth 10% of the project grade.
Submit any files which you have written and modified:
Submit the files using the procedure given to you for your section of the
course.
If your makefile is set up correctly, you should be able to execute the command
make submit.
There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.
If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check . Make sure they work. Do this before the due date.
Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/ . One
of the tools provided by the submit program is
submitls. It lists the names of
the files you have submitted.
Additionally, there are two programs for use only by CMSC-341 students (not
part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/
and are named submitmake
and submitrun. You can
use these programs to make or run your submitted projects.
The syntax is similar to that for submit:
submitmake <class> <project>
Example: submitmake cs341 Proj4
This makes the project, and shows you the report from the make utility. It
cleans up the directory after making the project (removes .o and ii_files), but
leaves the
executable in place.
submitrun <class> <project> [command-line args]
Example: submitrun cs341 Proj4 1234 1000 100
This runs the project, assuming there is an executable (i.e. submitmake was run successfully).
Your project will be tested using a variety of command
lines, some of which will be invalid.
Your project will also be tested using a variety of command files which will
test various conditions which your code should handle.
Project grading is described in the Project
Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project
Policy handout for further details on honesty in doing projects for this
course.
Remember, the due date is firm. Submittals made after