```
COMP 410, Fall 2012

Sample problems for Final Exam

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

linear                 hash into lists
probing

0: _________           0: _____

1: _________           1: _____

2: _________           2: _____

3: _________           3: _____

4: _________           4: _____

5: _________           5: _____

6: _________           6: _____

7: _________           7: _____

8: _________           8: _____

9: _________           9: _____

10: _________          10: _____

11: _________          11: _____

12: _________          12: _____

(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?

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

```