CSE 326

HW 3

Related reading: Chapters 4 & 5

Due date: Monday, April 23, 2001 in class

Total points: 30 points

1. Consider B-trees of order 3. Starting from an empty tree, show all the intermediate B-trees obtained by the following sequence of operations: add key 1, add key 2, add key 3, add key 4, add key 5, add key 6, add key 7, add key 8, add key 9, delete key 1, delete key 2, delete key 3, delete key 4, delete key 5, and delete key 6.
2. Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h(x) = x (mod 10), show the resulting:

1. Separate chaining hash table.
2. Open addressing hash table using linear probing.
3. Open addressing hash table using quadratic probing.
4. Open addressing hash table with second hash function h’(x) = 7 – (x mod 7).

1. A spelling checker reads an input file and prints out all the words not in some on-line dictionary. Suppose the dictionary contains 30,000 words and the file is large, so that the algorithm can make only one pass through the input file. A simple strategy is to read the dictionary into a hash table and look for each input word as it is read. Assuming that an average word is seven characters and that it is possible to store words of length L in L+1 bytes (so space waste is not much of a consideration), and assuming a quadratic probing hash table, how much space does this take?