Assignment $03$: Hashing

Possible points: $55$

Use the table below to convert a character key to an integer for the following questions.

Give the contents of the hash table that results when the following keys are inserted in that order into

an initially empty $13-$item hash table: $(E_1,A,S_1,Y,Q,U,E_2,S_2,T,$I,$O,N).$ Use $h(k)=$kmod$13$ for

the hash function for the $k-$th letter of the alphabet $($see above table for converting letter keys to

integer values$).$ Use double hashing and let $h^t(k)=1+(kmod11)$ be the secondary hash

function.

Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining

scheme to keep each list in sorted order. How does the professor's modification affect the running time for

successful searches, unsuccessful searches, insertions, and deletions?

$[15$ points

Using the following strategies, and given a hash table with $7$ entries, draw the hash table and it's contents

after inserting the following numbers: $7,11,71,42,13,49$ :

points$]$

$($a$)$ Separate chaining

$($b$)$ Linear probing

$($c$)$ Quadratic probing

$($d$)$ Double hashing

Calculate the load factor $$ for each of the strategies.

Submission

Please submit all the answers in a single PDF file.

If you submit HANDWRITTEN answers, please make sure they are clear to read. Otherwise, points will be

deducted.