Difference between revisions of "CISC220 F2021 Lab10"
From class_wiki
| Line 24: | Line 24: | ||
* '''(1 point)''' What are the "home positions" of every word? That is, what indices do they hash to before collisions are resolved? Either show your work or include your program code in the PDF. | * '''(1 point)''' What are the "home positions" of every word? That is, what indices do they hash to before collisions are resolved? Either show your work or include your program code in the PDF. | ||
| − | * '''(1 | + | * '''(1 point)''' Show the final hash table if the words are inserted in the order above using ''separate chaining'' for collision resolution. Each chain should be an unordered, singly-linked list with the newest item being inserted at the head of the list. |
* '''(1.5 points)''' Show the final hash table if the words are inserted in the order above using ''linear probing'' with a step size of 1. What is the total number of probes beyond the home position for each word? | * '''(1.5 points)''' Show the final hash table if the words are inserted in the order above using ''linear probing'' with a step size of 1. What is the total number of probes beyond the home position for each word? | ||
| − | * '''(1 | + | * '''(1.5 points)''' Suppose the table is ''rehashed'' during linear probing when the load factor exceeds 0.5. Let the new table size be 23, the smallest prime number greater than 2m. Show the new hash table both right after rehashing AND after all the words have been inserted. |
===2. Submission=== | ===2. Submission=== | ||
Latest revision as of 08:39, 18 November 2021
Lab #10
1. Written problems
Suppose you want to hash words into a hash table of size m. Let v_i be the English alphabet place value of the ith letter in a q-letter word W, where the value of 'a' = 0, 'b' = 1, ..., 'z' = 25. One possible hash function is
h(W) = [v_0 + v_1 + ... + v_(q-1)] mod m
For example, if m = 11 and W = "abc", then h("abc") = [0 + 1 + 2] mod 11 = 3
Assume m = 11 and you have the following list of words, in order:
- dog
- duck
- cow
- mouse
- horse
- sheep
- goat
- chicken
- pig
Please answer the following questions about the hash function, table, and list of words above. Feel free to write a short program to ensure that your calculations are correct.
- (1 point) What are the "home positions" of every word? That is, what indices do they hash to before collisions are resolved? Either show your work or include your program code in the PDF.
- (1 point) Show the final hash table if the words are inserted in the order above using separate chaining for collision resolution. Each chain should be an unordered, singly-linked list with the newest item being inserted at the head of the list.
- (1.5 points) Show the final hash table if the words are inserted in the order above using linear probing with a step size of 1. What is the total number of probes beyond the home position for each word?
- (1.5 points) Suppose the table is rehashed during linear probing when the load factor exceeds 0.5. Let the new table size be 23, the smallest prime number greater than 2m. Show the new hash table both right after rehashing AND after all the words have been inserted.
2. Submission
- Make a PDF file <Your Name>_Lab10_README.pdf with your answers to the written exercises
- No need to compress or archive the PDF, since that's all you're turning in.
- Submit it in Canvas by midnight at the end of Tuesday, November 30
