Homework due Monday March 23, 2020

NOTE:

1) Your homework must be handed in at the start of class

2) Your homework must be typed! Untyped ssignments will receive zero credit

3) Your assignment must have the following heading at the top of the assignment:

Your Name

Your student ID

COSC 311

Hashing Homework

Sample:

Joe Smith

E12340678

COSC 311

Hashing Homework

Watch the video on Hashing here

(https://youtu.be/HTTcTdV50Oo)

1) Some suggest that it is better to size a hash table to a power of 2 , for example N=2

if N=2

2) In the video, I originally said we should map 'A' to 0, 'B' to 1, 'C' to 2,......'Z' to 25. I later changed this 'A' to 1, 'B' to 2,.......,'Z' to 26. My concern was that the original encoding could map two or more distinct strings to the same value, even before calculating a value mod N. Provide an example of this (assuming the original encoding).

3) We wish to insert the following strings into a hash table:

BEN

AL

SUE

CHUCK

KAREN

MIKE

SAM

MIKE

ALICE

TARA

TIM

BOB

Let's make the hash table size p=19 ( 19 is a prime ). Use letter encodings where A maps to 1, B maps to 2, etc and strings map to powers of 26. For example, "ABC" would map to 1*(26^2) + 2*(26^1)+ 3*(26^0) mod 19 (you might find the web site Wolfram Alpha helpful. Just type in the expression as shown here).

a) show the hash tanle using linear probing

b) show the hash table using quadratic probing

c) show the hash table using a rehashing function. The rehashing function should be

stepSize = 7 - (f(s) mod 7)

d) which of the three resolution techniques worked the best? Support your answer.

4) It has been suggested that a perfect application for a hash table is a symbol table. Support this suggestion.