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.
  For for open addressing we need at least one table entry for each key. For double hashing we would want the size of the table to be prime. 7 is the smallest number that satisfies both conditions, although 11 and 13 would be good sizes too. A table size of 17 or higher is probably wasteful if you're only going to store 6 keys.
• 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.
  First, we compute the hash value for each key. hash(ripken) = 3, hash(murray) = 4, hash(palmer) = 1, hash(weaver) = 1, hash(robinson) = 4, and hash(thompson) = 6.

  0 null
  1   -> palmer -> weaver
  2 null
  3   -> ripken
  4   -> murray -> robinson 
  5 null
  6   -> thompson
  

• Show the resulting hash table when the keys after the keys are inserted and collisions are resolved using linear rehashing.
  

  0
  1 palmer
  2 weaver
  3 ripken
  4 murray
  5 robinson
  6 thompson
  

• Show the resulting hash table when collisions are resolved using double hashing where the secondary hash function is (key.length % (tableSize - 1)) + 1.
  The secondary hash values are hash2(ripken) = 1, hash2(murray) = 1, hash2(palmer) = 1, hash2(weaver) = 1, hash2(robinson) = 3, and hash2(thompson) = 3.

  0 robinson 
  1 palmer
  2 weaver 
  3 ripken
  4 murray
  5 
  6 thompson
  

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.
  The array elements would be 3 5 10 8 6 15 12 9 14 7 13 20 16 19.
• Draw the heap after inserting 4 and then 21.

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

• Draw the heap after two extract-min (dequeue) operations. Starting with the heap after the two insertions, we get

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