CSE 326, Spring 1995: Homework 8

Due 5/24/95

  1. (10 points) Consider the data 1,2,3,4,5,6 with respective frequencies .3, .1, .1, .1, .1, .3.
  2. (10 points) Suppose we wish to maintain a hash table of 30,000 words in the English language as part of a spell checker. The question is: which is the best way to store the table, open hashing with chaining or closed hashing with linear probing. Assume the queries to the dictionary are 90% successful and 10% unsuccessful. Assume that the average length of a dictionary word is 7 characters and that L characters takes L+1 bytes of storage. Assume that pointers and integers take 4 bytes of storage.
  3. Consider the problem of lazy deletion in closed hashing with linear probing. Assume we have an on going process of insertions, deletions, and finds. Design five algorithms where each algorithm is briefly described in pseudocode. Assume the keys are non-negative integers which are hashed into a table T of size HSize. You will need a marking array M to store whether a table entry is deleted or not. An empty table entry can be indicated using -1.