Part B: Problem $1$: $(25$ points$)$ Assume you are creating a hash table that uses chaining. Recall that the runtime depends on the load factor $=\frac{n}{m},$ where $n$ is the number of inserted items and $m$ is the number of slots.

The choice of $$ is important. Too high of an $$ means more collisions. Too low of an $$ means we are wasting space. Let ${}_L$ be our lower bound and ${}_H$ be our upper bound on $$ so that ${}_L{}_H.$

Answer the following questions:

$($a$)$ Modify CHAINED$-$HASH$-$INSERT $($T$,$ x $)$ to increase the size of the hash table if $$ exceeds or is equal to ${}_H.$ You can calculate your lower bound on the size of the table from ${}_L($i$.$e$.m=\frac{n}{{}_L}).$

$($b$)$ Modify CHAINED$-$HASH$-$DELETE $(T,x)$ to decrease the size of the hash table if $$ becomes less than or equal to ${}_L.$ You can calculate your upper bound on the size of the table from ${}_H($i$.$e$.m=\frac{n}{{}_H}).$

$($c$)$ Assume your hash table has $70$ elements and the table size is $100($i$.$e$.n=70,m=100,$ and $=0\mathrm{.}7).$ Let ${}_L=0\mathrm{.}375$ and ${}_H=0\mathrm{.}75.$ If you insert $10$ more items, what are $n,m,$ and $?$ How many more items do you need to add to the table before $m$ changes again? Graph $$ as $n$ increases on the interval $70n2000($e$.$g$.$ graph $$ as a function of $n$:$(n))$

$($d$)$ Describe the worst case runtime for CHAINED$-$HASH$-$INSERT$($T$,$ x$)?$ Describe the best case? Assuming that the maximum probability of the worst case is $\frac{1}{n},$ informally argue for an average case runtime is $(1).$

$($e$)$ Theorem $11\mathrm{.}2$ states that the average$-$case runtime for searching in a hash table with chaining is $(1+).$ Using this theorem along with our modifications to delete and insert, prove the following:

Show: Let ${}_L,{}_{H}in{R}^{+},$ If ${}_L{}_H,$ then the average$-$case runtime of search with chaining is $(1).$

$($Hint: What is the asymptotic runtime of $(n)?)$