COMP 410, Fall 2012


Sample problems for Midterm Exam 1

1)  (a) Below are two hash tables.  The left one will use linear probing
    to resolve collisions.  The right one will hash into lists to resolve
    collisions.  Fill in each table with the following input items in
    the order given left to right:

       alpha beta gamma delta epsilon zeta eta theta iota kappa lambda

    Use this hash function: 
      take the position in the alphabet of the first third letters, 
      add them; then multiply by the length of the word; then mod 
      the result by 13.
    Example: alpha  a is 1, p is 16, sum 17. 17*5 is 85. 85 mod 13 is 7
             so alpha hashes to slot 7.

an alphabet, with ordinal positions, for your viewing pleasure
A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26


   Answer:

    linear                 hash into lists
    probing

    0: iota                0: _____

    1: _________           1: _____ 

    2: delta               2: _____ --> zeta --> delta
 
    3: zeta                3: _____ 

    4: _________           4: _____
  
    5: eta                 5: _____--> kappa --> eta

    6: kappa               6: _____

    7: alpha               7: _____ --> lambda --> alpha

    8: theta               8: _____ --> theta

    9: gamma               9: _____ --> gamma

   10: beta               10: _____ --> beta

   11: lambda             11: _____

   12: epsilon            12: _____ --> iota --> epsilon


   (b) We ended up storing 11 items in the tables, and let's say we 
   expected to have 11 items for storage.  Was the choice of 13 for 
   table size a good one for the linear probing table?  If so, cool... 
   if not, what size would have been better?  

   Answer:
   13 is too small, we want a load of 1/2 so we need twice as many
   slots as items stored... so we expected 11 so we need a prime 
   larger than 22.. so 23 is better. We would adjust the hash function
   to mod 23


   Same question for the hash-into-lists table... was 13 a good size?  
   If so, cool, ... if not, what size would have been better?

   Answer:
   13 is ok here.  We want a load of 1, so with 11 items, we could do with
   11 slots (11 is prime)... but 13 is prime and close to 11 so its ok too.