COSC 311
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⁸ = 256. Suppose we have a string s and a hash function f( ), so that we map s to f(s) mod N. Show that f(s) mod N is the same as f(s) AND 255. That is, we only need to look at the 8 right most bits of f(s) to determine where it is mapped. Put another way,

if N=2^k , then (   f(s) mod N   )   =   (   f(s) AND (N-1)   )       AND refer to logical AND, or just look at the K rightmost bits of f(s). Why is this better than using a prime p ?


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.