Problem Set 6

Assigned: March 19
Due: March 26

If submitting by email, please send to Changle Wang < cl.wang@nyu.edu >

Problem 1

Suppose that we has a hash table of size 15 and we insert the keys 10, 24, 29, 43, 39, 21, 45, 14. Show the final state of the hash table, assuming we use:

Problem 2

Consider the following hash functions for strings that appear in text:
hash(S,N)  /* hash string S to a value between 0 and N-1 */
PRIME = 37;
SUM = 0;
for (i = 0; i < S.length(); i++) 
   SUM = ((PRIME * SUM) + CharToInt(S[i])) mod N;
return SUM

A. This works badly if the hash table size N happens to be a multiple of PRIME. Why?

B. This would work badly if we changed PRIME to be 1 or -1. Why?

C. This does work badly if the hash table size N happens to be a power of PRIME minus one (e.g. N = 372-1 = 1368). Why?

Problem 3

Suppose that we need to hash unlabelled binary trees. That is, we need a function that as arguments will take a hash table size N and a data structure like one of these

and returns a value between 0 and N-1. Design a suitable hash function. The hash function should have the following properties:

Problem 4

Modify problem 3 for the case where we don't care about the distinction between left and right child: That is, A and B are considered the same tree and should have the same hash value. Likewise C and D are considered the same tree and should have the same hash value. However, A and C are considered different trees and should have different hash values.