Harvard University Hashing Worksheet

Question 3: Hashing(a) Consider a table indexed from 0… 12 and where hashing is carried out using quadratic probing,
using the function h(k, i) = k + 4i + 2i2 mod 13. Show the result of the insertion of the following keys:
38, 16, 50, 7, 18, 19, 12, 37, 29, 2
, 22.
=
>
7
,)
(b) Using the quadratic probe sequence from part (a), write the pseudo-code for an algorithm called
HashInsert(T, k) that takes as input a hash table T[0,…, 12) and a key k to be inserted into the table.
Your algorithm must insert the item k into the table, using the probe sequence h(k, i) and return true if
the insertion is successful, and false otherwise.
*You do not have to check for duplicates (you can assume when inserting k that it is not already in the
table). You can assume that the table was initially empty and only inserts were carried out, no deletions
(c) Consider arrays A and B, each of which is indexed from 1 to n. The array entries are bank customer
PIN numbers, where a PIN number is a sequence of exactly 3 digits (ex. 460 or 013 are each valid PINs).
Array A consists of the PIN numbers of customers from bank A, and array B consists of the PIN numbers
of customers from bank B. Your job is to design an algorithm that outputs all safe passwords from bank
A. The safe passwords from bank A are those which are used by a customer from bank A but not also
used by a customer in bank B. Write the pseudo-code for your algorithm, and justify why it runs in time
O(n) in the worst-case.