CSE 326

HW 4

Related reading: Chapters 5&6

Due date: Friday, May 11, 2001 in class

Total points: 45 points

1. Leftover from homework #3:

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?

State the load factor (choose a value that is good for quadratic probing) and give your final answer in bytes. (Assume a pointer is 4 bytes and that the hash table is an array of pointers to words).

2. Show the result of inserting the keys 10111101, 00000010, 10011011, 10111110, 01111111, 01010001, 10010110, 00001011, 11001111, 10011110, 11011011, 00101011, 01100001, 11110000, 01101111 into an initially empty extensible hashing structure with M = 4.
3. If a d-heap is stored as an array, for an entry located in position i, where are the parents and children?
4. A min-max heap is a data structure that supports both deleteMin and deleteMax in O(log N) per operation. The structure is identical to a binary heap, but the heap-order property is as follows:

• For any node X at even depth, the element stored at X is smaller than the parent but larger than the grandparent (where this makes sense, i.e., when X has predecessors).
• For any node X at odd depth, the element stored at X is larger than the parent and smaller than the grandparent.
• The root is considered to be at depth 0.

1. Construct a min-max heap (tree) consisting of 25 nodes.
2. How do we find the minimum and maximum elements?
3. Give an algorithm to perform deleteMax. Apply your algorithm to remove the max of the tree you constructed in part (a) and show the resulting tree.

Here’s the 5^th question:

1. Show the result of the following sequence of instructions: union(1,2), union(3,4), union(3,5), union(1,7), union(3,6), union(8,9), union(1,8), union(3,10), union(3,11), union(3,12), union(3,13), union(14,15), union(16,0), union(14,16), union(1,3), union(1,14) when the unions are performed by height, and the find operations are performed with path compression on the deepest node.
2. Argue that if unions are performed by height, then the depth of any tree is O(log N). Present your argument as formally as possible.