Question $40$

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 Linear Probing displaying step by step $($redraw the Table after

every element is inserted one by one left to right$)$ from your list, apply the formula to map the

key into the table indexand 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$

$($your 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.