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.