CSIE
Algorithms (CS3001301)
Homework 3
Total: 10 pts
Problem 3.1. Consider inserting the keys 10, 22, 17, 28, 15, 4, 31, 88, 59 into a hash table of length 𝑚 = 11 using open addressing with the auxiliary hash function ℎ′(𝑘) = 𝑘 mod 𝑚. Illustrate the result of inserting these keys using linear probing, using quadratic probing with 𝑐1 = 1 and 𝑐2 = 3, and using double hashing with ℎ2(𝑘) = 1 + (𝑘 mod (𝑚 − 1)). (3 pts)
Problem 3.2. Suppose that we are storing a set of n keys into a hash table of size m, what is the best-case searching time, and what is the worst-case searching time? Write down your answer in the form of 𝑇(𝑛) = Θ(𝑔(𝑛)). Briefly discuss your answer.
Problem 3.3. Discuss when (1) we have a very small set of possible keys | U |; (2) we have a very large number of inserted keys n, relative to the number of all possible keys | U |, will hashing still be useful? Explain your answer. (2 pts)
Problem 3.4. If the order of the key insertion sequence is changed, will we obtain the same hashed result? Briefly discuss your answer.
Problem 3.5. Write pseudocode for HASH-DELETE (using the pseudo-codes similar to slides no. 24 & 25), and modify HASH-INSERT accordingly to handle this situation. Let us assume the link to the element that we want to delete has been given. (3 pts)
