1 attachmentsSlide 1 of 1attachment_1attachment_1
Unformatted Attachment Preview
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
(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.
Purchase answer to see full
Explanation & Answer:
User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.