Assignment 4 CET

Assignment details are as follows:

Assignment: Implementing Hash Tables and Collision Resolution

Part 1: Hash Function Basics

1. Write a program to implement a simple hash function using the modulus operator (key % table_size).
2. Insert a sequence of integer keys into an array of size 10.
3. Show where each key is placed, both with no collisions handled and with linear probing.

• Example input: [15, 25, 35, 45]
• Students should demonstrate step-by-step placement.

Part 2: Separate Chaining

1. Implement a hash table with separate chaining using linked lists.
2. Support the following operations:

• put(key, value)
• get(key)
• contains(key)
• remove(key)

1. Test the program by inserting at least 10 keys that produce collisions and demonstrate successful retrieval.

Part 3: Open Addressing Linear Probing

1. Implement the same hash table using open addressing with linear probing.
2. Insert values into the table and handle collisions using linear probing.
3. Write test cases where clustering occurs and show the runtime effect when searching for an element.

Part 4: Open Addressing Quadratic Probing

1. Modify the open addressing implementation to use quadratic probing.
2. Test with the same set of inputs as in Part 3, comparing the distribution of keys in the table.
3. Highlight cases where quadratic probing fails to find empty slots even though space is available.

Part 5: Analysis Questions (Short Answer)

Students should explain:

1. The difference between separate chaining and open addressing.
2. What causes primary clustering in linear probing, and how quadratic probing tries to fix it.
3. Why choosing a prime table size is important for quadratic probing.
4. Given a sequence of insertions, identify the load factor and decide when resizing should occur.

Deliverables

• Code: Implementations of chaining, linear probing, and quadratic probing.
• Report (23 pages):
• Screenshots of program execution with example input/output.
• Written answers to analysis questions.
• A short discussion of which method they would choose for a real-world application and why.