(a) Assume that we are using a hash table of size $m$. Show that if the universe $U$ has size $|U| > nm$, there is a subset of $U$ of size $n$ with the property that they all hash to the same position, so that the worst-case searching time for hashing with chaining is $\Theta(n)$.

(b) We are storing a set $S$ of $n$ numbers in a hash table $T[0..m-1]$ of size $m$ and we are choosing $m=n$. Should we resolve collisions with chaining or open addressing? Explain your answer.

In [ ]:

```
```