1. Give the contents of the hash table that results when you insert items
with the keys E A S Y Q U T I O N in that order into
an initially empty table of M = 5 lists, using standard chaining
with unordered lists. Use the hash function 11 k mod M to
transform the kth letter of the alphabet into a table
index, e.g., hash(I) = hash(9) = 99 % 5 = 4.
2. Give the contents of the hash table that results when you
insert items with the keys E A S Y Q U T I O N in that order
into an initially empty table of size M = 16 using
linear probing. Use the hash function 11k mod M to
transform the kth letter of the alphabet into a table index.
3. Consider a hash table of size m= 1000 and the hash function
h(k)= [m (kA (mod 1))] for A= (sqrt(5)-1)/2; the notation
[x] refers to the largest integer at most x. For example
[3.14]=3. Of course, x (mod 1) is the fractional part of x.
Compute the locations to which the keys
61, 62, 63, 64, 65 are mapped.
4. Suppose we wish to search a linked list of length n,
where each element contains a key k along with a hash value h(k).
Each key is a long character string. How might we take advantage
of the hash value when searching the list for an element with
a given key?
5. Draw the "jump" table for the string aabbaaabbb used in the Knuth-Morris-Pratt algorithm.
6. Here is another method for checking over a phone line
if two strings of bits a1a2...an
b1b2...bn are identical. Take a random prime number p between 2 and, say, n^2.
Answer yes if A (mod p) = B (mod p) and no otherwise,
where A and B denote the numbers
whose binary representation is a1...an and b1...bn, respectively.
Prove that the
probability of having a false positive (ie, a yes that should have
been a no) goes to 0 as n goes to infinity.
HINT: Use the fact that the number of primes less than n^2
is at least c n^2/log n, for some constant c>0.