# Harvard University Hashing Worksheet

Description

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
, 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.

attachment

8 Pages

Tags:
hash table

Hashing

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.

## Reviews, comments, and love from our customers and community:

### Article Writing

Keep doing what you do, I am really impressed by the work done.

Researcher

### PowerPoint Presentation

I am speechless…WoW! Thank you so much!

#### Stacy V.

Part-time student

### Dissertation & Thesis

This was a very well-written paper. Great work fast.

Student

### Annotated Bibliography

I love working with this company. You always go above and beyond and exceed my expectations every time.

Student

### Book Report / Review

I received my order wayyyyyyy sooner than I expected. Couldn’t ask for more.

Student

### Essay (Any Type)

On time, perfect paper

Student

### Case Study

Awesome! Great papers, and early!

#### Kaylin Green

Student

Thank you Dr. Rebecca for editing my essays! She completed my task literally in 3 hours. For sure will work with her again, she is great and follows all instructions

Researcher

### Critical Thinking / Review

Extremely thorough summary, understanding and examples found for social science readings, with edits made as needed and on time. Transparent

Customer

Perfect!

Student