## 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:
- A. Chaining, with the hash function h(k) = k mod 15.
- B. Linear probing, with h(k,i) = (k+i) mod 15.
- C. Double hashing with hash function (k + i * (1 + k mod 11)) mod 15.

### 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 = 37^{2}-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:
- In general, deleting a leaf or swapping the left and right child
at any level
of the tree will change the value of the hash function. Thus no two of
the trees shown above should have the same value, except by chance.
- The hash function should run in linear time.

### 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.