Problem 1: Hash Practice (6 points) (a) Insert integer keys…
Problem 1: Hash Practice (6 points) (a) Insert integer keys A = in order into a hash table of size 7 using the hash function \(h(k) = (10k + 4) \mod 7\). Each slot of the hash table stores a linked list of the keys hashing to that slot, with later insertions being appended to the end of the list. Draw a picture of the hash table after all keys have been inserted. (3 points) (b) Suppose the hash function were instead \(h(k) = (10 k + 4) \mod c\) for some positive integer \(c\). Find the smallest value of \(c\) such that no collisions occur when inserting the keys from A. (3 points) Hint: By the pigeonhole principle, at least one collision occurs for \(c < 7\). Problem 2: Open Address Hashing (4 points) Consider an open-address hash table with a size of \(m = 16\). A hashing function maps keys to a random slot in the table. There are no deletions. Give the upper bounds on the expected number of probes for a successful and unsuccessful search when the load factor is \(\alpha = 1/2\). Note: You do not need to calculate the final numerical value if the answer involves a function like \(\ln\). Congratulations, you are almost done with this quiz. DO NOT end the Honorlock session until you have submitted your work to Gradescope. When you have answered all questions: Use your smartphone to scan your answer sheet and save the scan as a PDF. Make sure your scan is clear and legible. Submit your PDF to Gradescope as follows: Email your PDF to yourself or save it to the cloud (Google Drive, etc.). Click this link to go to Gradescope to submit your work: Quiz 9 Return to this window and click the button below to agree to the honor statement. Click Submit Quiz to end the exam. End the Honorlock session.