Homework 4

Details

1. (15) Consider a hash table of size 11, where the hash function h(k) = k mod 11 is used to determine the primary position of a key k in the table. You are tasked with inserting the following keys into the hash table:

   Keys: 26, 12, 48, 36, 50, 37, 72, 92

   For each collision resolution strategy below, show the state of the hash table after inserting all keys. Clearly indicate the sequence of steps for resolving collisions and provide the final table.

   1. Use Open Hashing (Separate Chaining).
   2. Use Closed Hashing with Linear Probing.
   3. Use Closed Hashing with Double Hashing. Use the primary hash function h1(k) = k mod 11 and the secondary hash function h2(k) = 8 - (k mod 8). If a collision occurs at position i, resolve it by probing the next position using the formula:

      inext = (i + j · h2(k)) mod 11

      where j is the number of attempts to resolve the collision. Do not forget that j starts back at 0 for every new insertion.

   4. Compare and contrast how well each one performs.
2. (15) Given pattern needle and text heedlendlebadleednnnneeded, use each of the following search strategies to try to find the pattern in the text. For each, count the total number of comparisons and shifts made. Do not forget to give the shift table(s) for the appropriate algorithms.
   1. Naive start at the beginning and shift by one after a failed match.
   2. Horspool's Algorithm
   3. Boyer-Moore Algorithm