Question $41$

Concatenate all the following digits, $1093859,$ with $9$ in front of it and $1$ at the end and form a list.

Example: $1093459,$ after concatenation $910938591,$ the list: $9,1,0,9,3,8,5,9,1.$ Remove duplicates from it$.$

a$)$ Create a Hash Table using Quadratic Probing on paper displaying step by step $($redraw the Table after every element is insertedone by one left to right$)$ from your list, apply the formula to map the key into the table index and calculate the load factor after each insertion. Detect collisions and perform any required collision handling as you go$.$ Perform rehashing if appropriate.

Parameters of the table are the same as those we used in class: initial Table size $N=11$

$($vour indexes are from $0$ to $10),$ Load factor threshold is $0\mathrm{.}75,$ Rehashing occurs after $8$th

element $($when you are trying to insert the $9$th$),$ formula: index $=$ key $\%N.$

b$)$ If you performed any collision handling state when the handling occurred, which keys caused the collision and why and what was your result.

c$)$ insert numbers $20,21,22,23$ and $24$ in your already populated table $($after step a$)$ is completed$).$ Perform Rehashing if appropriate $($double the table size$).$ If you performed rehashing in a$)$ just add the numbers to your table.