| Date Assigned: | Fri Feb-9 |
| Date Due: | Mon Feb-12 |
1. Read section 26.5 on hashing. There will be a quiz on Monday covering the material in the book, which includes material beyond this assignment.
2. Second, you are to write a decent hash function over English words. This function should map English words into numbers in the range [0,size-1], where size is entered by the user. A decent hash function should minimize the number of collisions (that is, the number of words which share the same hash value).
3. To test your function, run it over all the 69,000+ words in words.txt with size set to 10,000. You should keep a count for each hash value of how many words map to that hash value. Then, print out the following information:
a. What was the total number of words and the total number of possible hash values.Hint 1: Once you get this working, try changing your hash function and seeing if it improves your median value as computed in (f), as you will be graded on how low this value gets.
b. How many hash values had zero words map to them.
c. Which hash value had the most words mapped to it, and how many words that was.
d. What was the average number of words mapped to each hash value.
e. What was the median number of words mapped to each hash value.
f. The median, again, but this time not counting the values which have no words mapped to them.
Hint 2: To run your program using words.txt as input, you can either do file I/O, or -- probably easier for most of you -- you can do the following:
a) Go to Project/Settings/Link and set your output file name to "c:\temp\asst33.exe"Hint 3: The last actual word in words.txt is "zymurgy", which you may take advantage of in your code (so, for example, you know when to stop reading words). Alternatively, and perhaps better yet, after that word is the word "_end_", which you may stop on (be sure not to include this word in your analysis, however).
b) Save words.txt to c:\temp\words.txt
c) Compile your program
d) Run a DOS Command Prompt (available via the Start button)
e) In the DOS window, type: "cd c:\temp"
f) Next, in the DOS window, type: asst33.exe < words.txt
Good luck.
DK