///////
//
// Student: Russell Lowke
//     T.F: Francis Crick
// Unit Nine, pencil-and-paper part 1 - question 3 [worth 2pts],  8/7/2002
//
// A hash table for c haracter strings contains 8 buckets, nbumbered 0 through 7.
// Open addressing with quadratic probing is used to insert items in the table.
// hasing function (poorly chosen) assigns to a characted string the number of characters
// in the string modulo 8.
//
// The following words are to be inserted in the table:
// THE, MY, AN, BY, DO, WE, IF, TO, GO
//
// a) Determine which string causes the table to overflow, and show the table
//    at the point at which it does so.

Assignments: THE = 3, MY = 2, AN = 2, BY = 2, DO = 2, WE = 2, IF = 2, TO = 2, GO = 2
Quatratic probing (n + ): 1, 4, 9, 16, 25, 36, 49, 64, 81

Hash Table:

0
1
2 MY
3 THE
4
5 
6 AN
7

Overfloaw at "BY"

// b) Suppose that double hashing is used.  The value of the second hash function is
//    1 for a noun or pronoun (WE, MY), 2 for a verb (DO, GO), 3 for an article (THE, AN),
//    and 4 for any other part of speech (the rest).  Show the final hash table at the point
//    at  which overflow occurs.

Assignments: THE = 3, MY = 2, AN = 2, BY = 2, DO = 2, WE = 2, IF = 2, TO = 2, GO = 2
double hash: THE = 3, MY = 1, AN = 3, BY = 4, DO = 2, WE = 1, IF = 4, TO = 4, GO = 2

Hash Table:

0 
1
2 MY
3 THE
4 DO
5 AN
6 BY
7 WE

Overfloaw at "IF"