Homework 5

Due: Thursday, December 1

Turn in this assignment on paper in class.

  1. Question R-9.7 of textbook (p. 417): Hash the values 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 and 5 into a hash table with 11 slots. Handle collisions by open chaining. Use the hash function:
        h(i) = (3 i + 5) mod 11

  2. Question R-9.8 of textbook (p. 417): Repeat the above using linear probing instead of open chaining.

  3. Question C-9.7 of textbook (p. 419): Suppose that we are not allowed to use a "deleted" marker in a hash table that uses linear probing. Describe a scheme that allows deletion in this hash table. Make sure that search still works.