Homework due Monday March 23, 2020
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 student ID
Watch the video on Hashing here
1) Some suggest that it is better to size a hash table to a power of 2 , for example N=28 =
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=2k , 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:
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.