Reference no: EM133477493

Assignment: Multiplication Factor and Technique of Collision Resolution

Objective: Objective of the homework is to reinforce the concepts related to one of the most important data structures: hash table.

Part A

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

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

III. Open addressing is another technique of collision resolution.

1. What are the three hashing techniques used in open addressing?

2. 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?

3. Which of the above techniques can generate secondary clustering? Explain how secondary clustering can be formed using an example.

4. Which of the above techniques can eliminate both primary clustering and secondary clustering? Explain using an example.

Part B: 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

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

1. INSERT_Account(T, x) // insert the bank account record x to the table

2. DELETE_Account(T, k) // delete the bank account record from the table where k is the account number

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

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

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