Multiplication Factor & Technique of Collision Resolution Questions

Homework 5: Submission Template
Part I
1. Your answer to question 1 is here. Make sure to include your
complete answer.
2. Your answer to question 2 is here. Make sure to include your
complete answer.
3. Your answer to question 3 is here. Make sure to include your
complete answer.
a)
b)
c)
d)
Part II
1. Copy and paste your complete program for part (a) here.
2. Copy and paste your complete program for part (b) here.
3. Upload your programs for part (a) and part (b) to google drive and
provide the links for your programs.
Link for the program for part (a)
Link for the program for pa
1|Page
Homework 5
Due: Saturday, July 1st by 11:59 pm Online.
————————————————————————————–Objective: Objective of the homework is to reinforce the concepts related to one
of the most important data structures: hash table.
Note: Use the homework #5 submission template given to submit your solutions to
this homework.
Part I – 30 Points
1. (5 points) Assume that a hash table has 11 slots and the hash function is h(k) = k mod 11.
Demonstrate the insertion into the hash table of the following sequence of keys with
collision resolved by chaining: 5, 28, 19, 15, 20, 33, 12, 17, 10, 13
Show all the steps
2. (5 points) Consider a hash table of size m=1000 and a corresponding hash function h(k)
given by the multiplication method for A  (5 – 1)/2 = 0.6180… (as discussed in the
lecture slides). Compute the locations to which the following sequence of keys are mapped:
61, 62, 63, 64, 65.
Show all the steps
3. (20 points) Open addressing is another technique of collision resolution.
a) [4 Pts] What are the three hashing techniques used in open addressing?
b) [6 Pts] Which of the above techniques can generate primary clustering? Explain how
primary clustering can be formed using an example. Why primary clustering is not
desirable?
c) [6 Pts] Which of the above techniques can generate secondary clustering? Explain how
secondary clustering can be formed using an example.
d) [4 Pts] Which of the above techniques can eliminate both primary clustering and
secondary clustering? Explain using an example.
Submission
Use the homework #5 submission template given to submit your solutions to this
homework.
2|Page
Part II – 70 Points
Programming Problem
Suppose you are implementing a dynamic set of bank account records as a hash table for the Sun
Devil Bank. Each bank record has an account number, owner’s name and the current balance. the
account number is any six-digit integer number between 100001 and 999999. No two records can
have the same account number. In addition to the key, each record has following information.
Even though the account number can take a value between 100001 and 999999. Even though the
account number gives a higher range of numbers bank will not have more than 800 accounts at a
given time.
Hash Table Implementation Details: You will implement this hash table in two ways as described
below. You need to design a suitable node structure for account record and then each slot on in the
hash table can be a pointer to an account record
a) [40 Points] Hashing chaining in case of collision. Hash function h(k) = k mod m
Assume that the hash key is k mod m and using chaining in case of a collision. The size (m) of
the hash table (T) is 753. Also, you can assume that account numbers are generated using a random
uniform distribution function and each account number is unique.
Write a C or C++ program that Implements the hash table construction for the above scenario and
then implement the following three functions
a) INSERT_Account(T, x) // insert the bank account record x to the table
b) DELETE_Account(T, k) // delete the bank account record from the table where
k is the account number
c) SEARCH_Account(T, k) //search the account number k in the hash table and
returns the corresponding bank account record and display account information
For the insert operation, read the owner’s name, account number and the account balance from the
keyboard. For delete and search operations, read the account number from the keyboard
Save your program as hash_chain.cpp or hash_chain.c
b)[ 30 Points] Hashing open addressing in case of collision. Use linear probing
h(k, i) = (h’(k) + i) mod m. i = 0, 1, 2, …, and h’(k) = k mod m
The size (m) of the hash table (T) is 753. Also, you can assume that account numbers are generated
using a random uniform distribution function and each account number is unique.
Write a C or C++ program that Implements the hash table construction for the above scenario and
then implement the following three functions
INSERT_Account(T, x) // insert the bank account record x to the table
SEARCH_Account(T, k) //search the account number k in the hash table and
returns the corresponding bank account record and display account information.
3|Page
For the insert operation, read the owner’s name, account number and the account balance from the
keyboard. For the search operations, read the account number from the keyboard
Save your program as hash_open.cpp or hash_open.c
Submission
Use the homework #5 submission template given to submit your solutions to this
homework.