Assignment 07: Key Index Searching & Sorting, Hashing

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
2. You may use any language to complete the tasks.
3. You need to submit the one single file containing all the methods/functions. No
late submissions will be considered.
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 FALL1 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.
Note: You may maintain another global variable(java)/instance variable(python) if needed (but
you can’t use more than one).
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