I just need help with 3.2~3.5, I included the first pic just in case that information is needed.

3. Hash Tables: Dealing with Collisions In a hash table, when two keys hash to the same location, we have a collision. There are multiple strategies for handling collisions: Separate chaining: each location in the table stores a chain (typically a linked list) of all keys that hashed to that location. Open addressing: each location in the table stores a key directly. In case of a collision when inserting, we probe the table to search for an available storage location. Similarly, in case of a collision when looking up a key k, we probe to search for k. Suppose our hash function is h, the size of the table is m, and we are attempting to insert or look up the key k: - Linear probing: on the ith attempt (counting from 0), we look at index (h(k)+i) Quadratic probing: on the th attempt (counting from 0), we look at index For insertion, we are searching for an empty slot to put the key in. For lookup mod m. (h(k) ) mod m. we are trying to find the key itself 3.1 You are given a hash table of size m with n inserted keys. Collisions are resolved using separate chaining. If n- 2m and the keys are not evenly distributed, what is the worst-case runtime complexity of searching for a specific key using big-O notation? Under the same conditions, except that now the keys are evenly distributed, what is the worst-case runtime complexity of searching for a specific key using big O notation? As usual, for both of the answers above, give the tightest, simplest bound. For the next three questions, you are given a hash table of capacity m- 13. The hash function is h(k) ; after hashing we attempt to insert the key k at array index h(k) mod m. Like the code from lecture, we insert at the beginning of an existing chain. 3.2 Assume the table resolves collisions using separate chaining. Show how the set of keys below will be stored in the hash table by drawing the final state of each chain of the table after all of the keys are inserted, one by one, in the order shown. 67, 23, 54, 88, 39, 75, 49, 5 Wherever they occur, you should indicate NULL pointers explicitly by the nota- tion from class: 4 10 12 3.3 Show where the sequence of keys shown below are stored in the same hash ta ble if they are inserted one by one, in the order shown, using linear probing to 67, 23, 54, 88, 39, 75, 49, 5 0 1 2 3 4 5 6 7 89 10 11 12 resolve collisions 3.4 Show where the sequence of keys shown below are stored in the same hash table if they are inserted one by one, in the order shown, using quadratic probing to 67, 23, 54, 88, 39, 75, 49, 5 0 1 23 4 56 7 89 10 11 12 resolve collisions. 3.5 Quadratic probing suffers from one problem that linear probing does not. In particular, given a non-full hash table, insertions with linear probing will always succeed, while insertions with quadratic probing might not (i.e., they may never find an open spot to insert). Using h(k)-k as your hash function and m 7 as your table capacity, give an example of a table with load factor not above 2/3 and a key that cannot be successfully inserted into the table. (Hint: start entering different multiples of 7.) Key that cannot successfully be inserted