CPSC 2150 – Algorithms and Data Structure II Assignment 5: Hashing Total – 90 Marks___________ Learning Outcomes • Practice on hashing and resolving collisions • Implementing and programming with C++ Resources • Chapter 9 of the text book Description Exercise 1 – [39 marks] You have a hash table of size m = 11 and two hash functions h1 and h2: h1(x) = (sum of the values of the first and last letters of x) mod m h2(x) = ((value of the last letter) mod (m − 1)) +1 where the value of a letter is its position in the alphabet (e.g., value(a)=1, value(b)=2, etc.). Here are some precomputed hash values: word: ape bat bird carp dog hare ibex mud koala stork h1: 6 0 6 8 0 2 0 6 1 8 h2: 6 1 5 7 8 6 5 5 2 2 A. [10 marks] Draw a picture of the resulting hash table after inserting, in order, the following words: ibex, hare, ape, bat, koala, mud, dog, carp, stork. B. [3 marks] Highlight cells that are looked at when trying to find bird. Do part A and B for each of the following techniques: 1. Separate chaining with h1 as your hash function. 2. Linear probing with h1 as your hash function. 3. Double hashing with h1 as your first hash function and h2 as your second hash function. Exercise 2 – Hash worse case: A hash table of size M stores N integer keys. Collisions are handled by chaining and the hash function is h(K) = K mod M. 1. [8 marks] What is the worst-case search time? Give an example of a set of keys that achieves the worst-case search time. 2. [3 marks] Would you use this hash table for a time-critical application (e.g., air traffic control)? Exercise 3 – Linear probing with load factor: Demonstrate the insertion of the keys 5,28,19,15,20,33 into a hash table with collisions resolved by linear probing. Assume that the hash table has m slots (m=7) and its load factor is 0.70 and the hash function is h(k) = k mod m. For rehashing, choose the closest prime number less than twice of current m as the new value of m. [15 marks] Draw the state of the hash table after every insertion. Exercise 4 – Symbol table: Given your passion for computer science (and for finding a well-paying job) it is expected that you will continue taking more CS courses. Now, when you take a course on compilers later, you will be asked to implement such a creature. As you may expect, this is not trivial, so start thinking about it. Now. Good. (See, we care about you!) Well, your compiler will read a file containing the source program in some language, and will encounter variable names, function names, and procedure names. Let us call all of these names. For each name, you will need to keep a record with some information associated with it in some neat data structure. Now, every time a name is encountered, you may need to: 1. Check to see if you did encounter it before. If you did not, you have to insert it into your neat data structure. 2. If it is a name that you have seen before, retrieve some of the values associated with it. 3. When you are changing scope by entering or exiting a function declaration, you will need to delete some names. [25 marks] You have the following options for implementing your neat data structure: array, linked list, balanced binary tree and hash table. Investigate the options by creating a table that gives for each implementation, the expected time of the insert, retrieve, and delete operations. Explain your answers and discuss the advantages and disadvantages of each implementation for the above name handling application. Please clarify your assumptions. SUBMIT to D2L Submit a zip file named StudentNumber-Asgn5.zip including answers.pdf file by the due date. For example, if your student number is 10023449, the submitted file must be named as 10023449-Asgn5.zip.
