DOC PREVIEW
GSU CSC 2320 - Project Final (team)

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSCI 2320 Data Structure Final Group Project(3 members in a group)Hash Tables with Quadratic probing and Double Hashing Executive Summary:A hash table is a data structure that uses a hash function to efficiently map certainidentifiers or keys (e.g., person names) to associated values (e.g., their telephonenumbers). The hash function is used to transform the key into the index (the hash) of anarray element (the slot or bucket) where the corresponding value is to be sought.You are asked to use quadratic probing and double hashing to implement the hashfunction with a given action file. Project Objective: in completing this project, you will- Enhance your ability to hash tables- Familiar with different probing approaches- Enable yourself to perform the analysis of different hash function with the samegiven array sizeDue Dates and Honor:This project will be due by the beginning of the class on Monday April/25/2011.This is an independent team programming project, and it is very important that youunderstand and abide by the policy concerning programming projects. Remember, yourpersonal honor and integrity is far more important than your grade on the project. Detailed Specification:1. Download the action file and read the file in your program. Each rowrepresents one number. If the number does not appear in the hash table, itmeans “store number”. If the number exists in the hash table, it means “deletenumber” 2. Create an empty array with size variable m3. Write a quadratic probing function (h(k, i ) = (h(k) + c1*i + c2*i^2) mod m)with function parameter m for hash function (h(k) = k mod m) and c1 and c2changeable.4. Write a double hashing function (h(k, i ) = (h1(k) + ih2(k) + i) mod m) withfunction parameter m1 for hash function (h1(k) = k mod m1) and m2 for hashfunction (h2(k) = k mod m2) changeable.5. Define your own hash function that is different with (3) and (4)6. Write a hash table print out function, which generates all executed records.(used for 1st file only) The table generated by the program should looks like:Action 0 1 2 3 4 5 6 7 #probeStore 8 8 1Store 20 8 20…After you finished all functions, following are the things you need to carry out:For file 1:1.1. Use quadratic probing approach to deal with the action file, while m=8,c1=1, c2=0. Print out the entire hash table through your print function.1.2. Use quadratic probing approach to deal with the action file, while m=8,c1=0, c2=1. Print out the entire hash table through your print function.1.3. Use quadratic probing approach to deal with the action file, while m=8,c1=1, c2=2. Print out the entire hash table through your print function.1.4. Use quadratic probing approach to deal with the action file, while m=8,define your own c1 and c2 that generates the best result. (At least 10 differentnumbers need to be checked) Print out the entire hash table through your printfunction.1.5. Use double hashing approach to deal with the action file, while m1=8,m2=3. Print out the entire hash table through your print function.1.6. Use double hashing approach to deal with the action file, while m1=8, defineyour own m2 that generates the best result. (At least 10 different numbers need tobe checked) Print out the entire hash table through your print function.1.7 Find the best result for the hash function you defined while the given arraysize is 8. Report your best parameters. Print out the entire hash table throughyour print function.For file 2:2.1. Use quadratic probing approach to deal with the action file, while m=211,c1=1, c2=0. Record the total probe# and calculate the average probe#.2.2. Use quadratic probing approach to deal with the action file, while m=211,c1=0, c2=1. Record the total probe# and calculate the average probe#.2.3. Use quadratic probing approach to deal with the action file, while m=211,c1=1, c2=2. Record the total probe# and calculate the average probe#.2.4. Use quadratic probing approach to deal with the action file, while m=211,define your own c1 and c2 that generates the best result. Record the total probe#and calculate the average probe# for at least 10 different settings . And thenreport your best finding.2.5. Use double hashing approach to deal with the action file, while m1=211,m2=113. Record the total probe# and calculate the average probe#.2.6. Use double hashing approach to play with your hash function, find your own(best) m1=211 and m2 which generates the best result. Record the total probe#and calculate the average probe# for at least 10 different settings . And thenreport your best finding.2.7 Find the best result for the hash function you defined while the given arraysize is 211. Report your best parameters. Print out the entire hash table throughyour print function.What to Submit:- A print out results of your program (specify with approach name and parameters)- Source code of your program.- A 10 minutes power-point presentation to explain the hash function youdeveloped and your group’s comparison


View Full Document

GSU CSC 2320 - Project Final (team)

Download Project Final (team)
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Project Final (team) and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Project Final (team) 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?