Projects

1. Complete the implementation of the ChainedHashTable class declared in Program  by providing suitable definitions for the following member functions: IsMember, CompareTo, Accept and NewIterator. Write a test program and test your implementation.
2. Complete the implementation of the ChainedScatterTable class declared in Program  by providing suitable definitions for the following member functions: IsFull, IsMember, CompareTo, Accept and NewIterator. Write a test program and test your implementation.
3. Complete the implementation of the ChainedScatterTable class declared in Program  by providing suitable definitions for the following member functions: IsFull, IsMember, FindInstance, CompareTo, Accept and NewIterator. Write a test program and test your implementation.
4. The Withdraw routine defined in Program  has been written under the assumption that linear probing is used. Therefore, it does not call explicitly the collision resolution function C. Rewrite the Withdraw routine so that it works correctly regardless of the collision resolution strategy used.
5. Consider an application that has the following profile: First, n symbols (character strings) are read in. As each symbol is read, it is assigned an ordinal number from 1 to n. Then, a large number of operations are performed. In each operation we are given either a symbol or a number and we need to determine its mate. Design, implement and test a data structure that provides both mappings in O(1) time.
6. Spelling checkers are often implemented using hashing. However, the space required to store all the words in a complete dictionary is usually prohibitive. An alternative solution is to use a very large array of bits. The array is initialized as follows: First, all the bits are set to zero. Then for each word w in the dictionary, we set bit h(w) to one, where is a suitable hash function.

   To check the spelling in a given document, we hash the words in the document one-by-one and examine the corresponding bit of the array. If the bit is a zero, the word does not appear in the dictionary and we conclude that it is misspelled. Note if the bit is a one, the word may still be misspelled, but we cannot tell.

   Design and implement a spelling checker. Hint: Use the SetAsBitVector class given in Chapter .

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.