COS 226 Homework #3
Due: Friday, February 25, 2005
Written Exercises
Follow the instructions on the assignments
page on how and when to turn these in. Each of these problems is worth 4
points. Be sure to also complete the programming part
of this assignment, including the written program report.
- [Exercise 14.17] Give the contents of the hash table that results
when you insert items with the keys E A S Y Q U T I O N in that order into
an initially empty table of M = 5 lists, using separate chaining with
unordered lists. Use the hash function 11 k mod M to
transform the kth letter of the alphabet into a table index, e.g.,
hash(I) = hash(9) = 99 mod 5 = 4.
- [Exercise 14.25] Give the contents of the hash table that results
when you insert items with the keys E A S Y Q U T I O N in that order into
an initially empty table of size M = 16 using linear probing.
Use the hash function 11k mod M to transform the kth
letter of the alphabet into a table index.
- [Exercise 14.32] Give the contents of the hash table that results
when you insert items with the keys E A S Y Q U T I O N in that order into
an initially empty table of size M = 16 using double hashing.
Use the hash function 11k mod M for the initial probe and the
second hash function (k mod 3) + 1 for the search increment.