Problem 1 In this problem, we analyze the amortized cost of hashing under dynamic resizing. For all subproblems, assume that inserting and deleting an element have actual cost 1, creating new hash tables have actual cost 0, and moving each element from an old table to a new table has cost 1. 1. (10%) Starting with a hash table of size 2k, load factor 1, perform deletion only. Whenever the load factor reaches 0.5, we create a new table with half the size and move all elements from the old table to the new table. Find the smallest amortized cost of each of these deletion operations. Prove your answer formally. Proving any constant amortized cost gives a good partial score. 2. (10%) Starting with an empty hash table of size 1, perform insertion and deletion in arbitrary ordering. Whenever the load factor is strictly less than 0.5, we create a new table with half the size and move all elements from the old table to the new table. Whenever the load factor reaches 1, we create a double-sized table and move all elements from the old table to the new one. Is it possible to prove a constant amortized cost for each operation? Prove your answer.