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.
   • Construct the 6 by 6 table which in entry (i,j) has the cost of the optimum binary search tree on data i,i+1,...,j and the root of the binary search tree with minimum cost.
   • Construct the optimum binary search tree on all the nodes 1 through 6 using the table constructed above.
   • Is there more than one optimam binary search tree?
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.
   • Given a hash table of size S how much storage for the dictionary is required for open hashing and for closed hashing? For closed hashing assume S > 30,000 and the hash table is an array of pointers.
   • Given a hash table of size S what is the expected number of comparisons per query for open hashing with chaining and for closed hashing with linear probing?
   • Suppose we desire 1.5 comparisons per query, what size table should we choose for open hashing with chaining and for closed hashing with linear probing?
   • Which data structure would you choose to solve the problem of building a hash table of 30,000 words as part of a spell checker and why?
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.
   • (10 points) "Find(x)" which returns the index of where x is stored if it is in the table and -1 otherwise. Find(x) will return -1 if x is marked as deleted in the table.
   • "Insert-new(x)" which inserts x into the table with the precondition that x is not currently in the table.
   • "Insert(x)" which inserts x into the table with no precondition on whether x is currently in the table or not.
   • "Delete(x)" which removes x from the table using lazy deletion (marking).
   • "Rehash(T)" which returns a new table of the same size HSize which contains all the items of the old table, but has no items marked as deleted.