## 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 = 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:
• 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.