4. (3 points) In the worst case, how many probes are required to insert N keys into an initially empty hash table using linear probing? Explain how this can happen. 5. Assume we have an initially empty hash table which uses linear probing and the hash function h(%) = 11k mod M Further, assume that we insert items with keys 4, 0, 18, 24, 16, 20, 19, 8, 14, 13 in that order. Give the contents of the hash table for each of the following table sizes: (a) (3 points) M = 16 (b) (3 points) M = 10 6. Say you are given a hash table size of M = 1123 and we insert keys into the table where collisions are resolved with linear probing. Assume we are using a good hash function that effectively hashes to a random cell . a F if 2a)) ave probes/hit = (1+ , ave probes/miss = 1+ 2 | (1- a)? (a) (2 points) What is the highest number of keys N I can put in the table if I want the average number of probes on a miss to be 18? (b) (2 points) How about 8