Description

CSE 220: Data Structures
Assignment 07: Key Index Searching & Sorting, Hashing
Instructions for students:

1. Complete the following problem using concepts of Key index searching,sorting and hashing
4. The submission format MUST be maintained. You need to copy paste all your codes in ONE SINGLE .txt file and upload that. If format is not maintained, whole lab submission will be canceled.
5. If you are using JAVA, you must include the main method as well which should test your other methods and print the outputs according to the tasks.
6. If you are using PYTHON, make sure your code has the methods invoked and proper printing statements according to the tasks.
7. The google form link for this lab is provided in BUX under LAB 7- subsection in the SUMMER1 CSE220 lab tab.

Task 1 on Key index Searching & Sorting (25 marks)
Create a KeyIndex class with the following properties :

Fields:

int [ ] k;

Description
An array of integers.

Constructor:(10 marks)
KeyIndex(int [ ]a)

Description:

This constructor takes an array of integers a and populates array k with the element in a as indices into k.

Note: make sure the build-up of your array k supports negative and non-distinct integers.
Methods:

search (int val) (5 marks)
Description:
This method searches for the value val within the array and returns true if found or false otherwise.
sort () (10 marks)
Description:

This method will return the sorted form of the array that had been passed into the constructor.
NOTE: Create a tester class or write tester statements to check whether the methods in your KeyIndex
class work properly. You need to submit both the classes as a part of your assignment. (5 marks)

Task 2 on Hashing (15 marks)

Given an array containing Strings, you need to write a code to store them in a hashtable. Assume that the Strings contain a combination of capital letters and numbers, and the String array will contain no more than 9 values.Use the hash function to be the
(total number of consonants*24 + summation of the digits) %9. In case of a collision, use linear probing.
For a String “ST1E89B8A32”, it’s hash function will produce the
value=(3*24+(1+8+9+8+3+2))%9=4, hence it will be stored in index 4 of the hash table.

Marks distribution:
1. Hash function calculation, method properly written =10 marks
2. Linear probing properly implemented= 5 marks