1.Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the pro- fessors modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?

2.Suppose that we are storing a set of n keys into a hash table of size m. Show that if the keys are drawn from a universe U with jU j > nm, then U has a subset of size nconsisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is .n/.

3.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 values when searching the list for an element with a given key?