Description

CS 300 Data Structures

Homework 3

PLEASE NOTE:
• SOLUTIONS HAVE TO BE YOUR OWN. NO COLLABORATION OR COOPERATION AMONG STUDENTS IS PERMITTED.
• 10% PENALTY WILL BE INCURRED FOR EACH DAY OF OVERTIME. SUBMISSIONS THAT ARE LATE MORE THAN 3 DAYS WILL NOT GET ANY CREDITS.
• SUBMISSIONS WILL BE MADE TO THE SUCOURSE SERVER. NO OTHER METHOD OF SUBMISSION WILL BE ACCEPTED.

The intention of this homework is to make you understand program instrumentation and performance measurement and compare your real results with analytical complexity. You will also understand the details of hash tables.
In this homework, you will measure and analyze the performance of hash-tables with linear probing. You will perform the following:

1. You will create a hash table of integers employing linear probing of the appropriate size (call this M)

2. You will randomly generate hash-table transactions (that is, inserts, deletes and finds). You can assume that inserts, deletes and finds occur in proportion i:d:f where i+d+f=8 and none of i, d, or f equal to 0, and i > d (so the load factor monotonically grows) and d,f ≥ 1. So, you can decide (randomly) on the type of a transaction by generating a random integer t, and then computing m = t mod 8. If m is between 0 and i – 1, then decide on an insert transaction, if m is between i and i+d–1, then decide on a delete transaction, otherwise decide on a find transaction. Assuming the random number generator is giving out truly random numbers, this procedure should approximate the desired transaction probabilities satisfactorily when you have a large number of transactions.

There are 8 possible combinations of the parameters satisfying the requirements, but we suggest that you experiment with only 3 of them :
i d f
6 1 1
4 2 2
2 1 5

3. Before each transaction you will note
• the type of the transaction,
• the current load factor of the hash table (l= N / M where N is the number of entries currently in the hash table)
and after the transaction is complete you will note • whether the transaction succeeded or failed
• how many probes were conducted.

4. You can generate the integers to be used for each transaction again using the random number generator. It would better to limit the range of the integers to 10M so that most integers have a decent chance of being deleted or searched. You can generate such integers by generating a
random number and taking mod 10M.

5. You should generate transactions until the either the table becomes full or you have a total of 1,000,000 transactions.

6. You should output your statistical data in a format (say comma or tab separated format) that can be imported into Microsoft Excel or Open Office Spreadsheet. You should figure out how to do this.

8. You should either use a hash function like x mod M that we used in class or another hash function of your choice that is suitable for linear probing (like extracting some bits from the middle of the integer (using bit operations) and then treating these bits as an unsigned integer and then computing that integer modulo M. You can do research on the web or in other books in the library for interesting integer hash function to use.

9. You should use the hash-table implementation with linear probing given in the text book. However, you will need to modify this implementation, so that the resizing operation is removed (just for the sake of this homework, though!). Another important change will be to change the findpos(x) method so that it handles deleted items properly; the code in the course slides assumes that deleted items are skipped over when inserting new items. This implies an insert is implemented by actually a find followed by an insert if find fails. You should also add new private data items and possibly new private methods so that you can keep the statistics properly, and modify the implementation of the methods (such as insert, delete and find) so that the number of probes are counted properly and recorded.

At the end of the homework, you should submit the following:

1. A short report (as a word or pdf document)
• Describing the changes you made to the hash table code to implement linear probing and keeping statistics and the hash function you chose to use.

• Showing the graphics you obtained from the statistics you collected in your runs. Please make sure that your plots are accurate and readable with the curves and axes appropriately labeled.

• Ending with any conclusions you can draw from your results.

2. Your source code files.

You should follow the following steps:

• Name the folder containing your source files as XXXXX-NameLastname where XXXXX is your student number. Make sure you do NOT use any Turkish characters in the folder name. You should remove any folders containing executables (Debug or Release), since they take up too much space. You should also put your report file labeled as XXXXXNameLastname.doc or XXXXX-NameLastname.pdf in this directory.
• Use the Winzip program to compress your folder to a compressed file named XXXX- NameLastname.zip. After you compress, please make sure it uncompresses properly and the uncompress produces the original folder exactly.
• Submit this compressed file in accordance with the deadlines above.

If the file you submitted is not labeled properly as above, if it does not uncompress, if the source code(s) do(es) not compile and if we can not open and print your report file, we regretfully will have to give you 0 credits for the homework. So please make sure all these steps work properly.