Due

Problem 1: Suppose the following keys are to be stored in a hash table. ripken, murray, palmer, weaver, robinson, thompson. Let the hash function be ((value(key[0]) + value(key[key.length - 1]) * key.length) % tableSize where key.length gives the length of a key, key[i] gives the character at the ith position of a key, and value(ch) returns the numeric value of the given letter (a = 1, b = 2, etc).

• Pick a good size for a hash table to store the six key values.
• Show the resulting hash table when the keys are inserted in the order listed above using external chaining with a sorted linked list as the secondary structure.
• Show the resulting hash table when the keys after the keys are inserted and collisions are resolved using linear rehashing.
• Show the resulting hash table when collisions are resolved using double hashing where the secondary hash function is (key.length % (tableSize - 1)) + 1.

Problem 2: Consider the following ASCII art heap.

                            3
                    /               \
            5                               10
        /       \                       /       \
    8               6               15              12
  /   \           /   \           /    \          / 
9       14      7       13      20       16     19

• Show how the given heap would be stored in an array.
• Draw the heap after inserting 4 and then 21.
• Draw the heap after two extract-min (dequeue) operations.