Part B: Problem 1: Assume you are creating a hash table that uses chaining. Recall that the runtime depends on the load factor a = where n is the number of inserted items and m is the number of slots. TIL The choice of a is important. Too high of an a means more collisions. Too low of an a means we are wasting space. Let α be our lower bound and aд be our upper bound on a so that a ≤ a ≤αд. Answer the following questions: (a) Modify CHAINED-HASH-INSERT (T, x) to increase the size of the hash table if a exceeds or is equal to aд. You can calculate your lower bound on the size of the table from a (i.e. m = "L). CXL (b) Modify CHAINED-HASH-DELETE (T, x) to decrease the size of the hash ta- ble if a becomes less than or equal to L. You can calculate your upper bound on the size of the table from αд (i.c. m = TL). απ (c) Assume your hash table has 70 elements and the table size is 100 (i.c. n = 70, m = 100, and a = 0.7). Let OL = 0.375 and 0.75. If you insert 10 more items, what are n, m, and a? How many more items do you need to add to the table before m changes again? Graph a as n increases on the interval 70 ≤ n ≤ 2000 (e.g. graph a as a function of n: a(n)) (d) Describe the worst case runtime for CHAINED-HASH-INSERT(T, x)? De- scribe the best case? Assuming that the maximum probability of the worst case is, informally argue for an average case runtime is (1). (e) Theorem 11.2 states that the average-case runtime for searching in a hash table with chaining is (1 + a). Using this theorem along with our mod- ifications to delete and insert, prove the following: Show: Let αL,Qμ € R*, If αL ≤ α ≤ αн, then the average-case runtime of search with chaining is (1). (Hint: What is the asymptotic runtime of a(n)?)

Part B: Problem 1: Assume you are creating a hash table that uses chaining. Recall that the runtime depends on the load factor a = where n is the number of inserted items and m is the number of slots. TIL The choice of a is important. Too high of an a means more collisions. Too low of an a means we are wasting space. Let α be our lower bound and aд be our upper bound on a so that a ≤ a ≤αд. Answer the following questions: (a) Modify CHAINED-HASH-INSERT (T, x) to increase the size of the hash table if a exceeds or is equal to aд. You can calculate your lower bound on the size of the table from a (i.e. m = "L). CXL (b) Modify CHAINED-HASH-DELETE (T, x) to decrease the size of the hash ta- ble if a becomes less than or equal to L. You can calculate your upper bound on the size of the table from αд (i.c. m = TL). απ (c) Assume your hash table has 70 elements and the table size is 100 (i.c. n = 70, m = 100, and a = 0.7). Let OL = 0.375 and 0.75. If you insert 10 more items, what are n, m, and a? How many more items do you need to add to the table before m changes again? Graph a as n increases on the interval 70 ≤ n ≤ 2000 (e.g. graph a as a function of n: a(n)) (d) Describe the worst case runtime for CHAINED-HASH-INSERT(T, x)? De- scribe the best case? Assuming that the maximum probability of the worst case is, informally argue for an average case runtime is (1). (e) Theorem 11.2 states that the average-case runtime for searching in a hash table with chaining is (1 + a). Using this theorem along with our mod- ifications to delete and insert, prove the following: Show: Let αL,Qμ € R*, If αL ≤ α ≤ αн, then the average-case runtime of search with chaining is (1). (Hint: What is the asymptotic runtime of a(n)?)