Exercise 6        Name __________________        Score __/15
Document last modified: 

1. (3) Exercise 11.1-1
2. (6) Exercise 11.1-2 - Describe how to use a bit vector of length m to represent a dynamic set of distinct elements numbered from 0 to m-1 with no satellite data. Dictionary operations should run in O(1) time. Assume m is greater than the computer word size. Give details of dictionary operations search, insert and delete.
3. (6)

1. Demonstrate the insertion of of the keys 12, 15, 6, 3, 7, 9, 13, 4, 5, 11, 21, 10, 8 into a hash table with collisions resolved by chaining. Let the table have 4 slots and the hash function be h(k) = k mod 4.
2. Find the largest number of key comparisons in a successful search in this table.  
3. What is the loading factor?
4. What is the expected comparisons for an unsuccessful search?
5. How many comparisons are required for a successful search for each key?
6. Find the average number of key comparisons in a successful search in this table.