Hashing 130 points We first provide a summary of what you will have to do for th

Hashing 130 points
We first provide a summary of what you will have to do for this question. The deliverables
and output format will be provided at the end of the file. You will test each hashing
implementation with the following:
A) The total number of elements in the table (N), the size of the table (T), the load factor
(N/T), the total number of collisions (C), and the average number of collisions (C/N).
B) You will check whether each word in another given file, query_words.txt, is in the hash
table, and print corresponding output depending on whether the word is found and not
found, and how many probes it took to find the word if it exists. Although you are
provided with a file, we will use an unseen test file with another file name, which may
contain any subset of words from words.txt.
To implement the above, you will write a test program named create_and_test_hash.cc .
Your programs should run from the terminal like so:
./create_and_test_hash        
should be “quadratic” for quadratic probing, “linear” for linear probing, and “double”
for double hashing.
For example, you can write on the terminal:
./create_and_test_hash words.txt    query_words.txt    quadratic
You can use the provided makefile in order to compile and test your code.
For double hashing, the format will be slightly different, namely as follows:
./create_and_test_hash words.txt    query_words.txt    double   
The R value should be used in your implementation of the double hashing technique
discussed in class and described in the textbook: hash2 (x) = R – (x mod R).
Part 1 (30 points)
Modify the code provided, for quadratic and test create_and_test_hash. Create a new file
linear_probing.h for linear probing.
Do NOT write any functionality inside the main() function within
create_and_test_hash.cc. Write all functionality inside the testWrapperFunction()
within that file. We will be using our own main, directly calling testWrapperFunction().
You will print the values mentioned in A) and B) above. See end of document for details on
how to print these values.
Part 2 (45 points)
Write code to implement double_hashing.h, and test using create_and_test_hash.
This will be a variation on quadratic probing. The difference will lie in the function
FindPos(), that has to now provide probes using a different strategy. As the second hash
function, use the one discussed in class and found in the textbook hash2 (x) = R – (x mod R).
We will test your code with our own R values. Further, please specify which R values you
used for testing your program inside your README.
Remember to NOT have any functionality inside the main() of create_and_test_hash.cc
You will print the current R value, the values mentioned in A) and B) above. See end of
document for details on how to print these values.
Part 3 (55 points)
Now you are ready to implement a spell checker by using a linear or quadratic or double
hashing algorithm. Given a document, your program should output all of the correctly
spelled words, labeled as such, and all of the misspelled words. For each misspelled word
you should provide a list of candidate corrections from the dictionary, that can be formed by
applying one of the following rules to the misspelled word:
a) Adding one character in any possible position
b) Removing one character from the word
c) Swapping adjacent characters in the word
Your program should run as follows:
./spell_check       
You will be provided with a small document named document1_short.txt, document_1.txt,
and a dictionary file with approximately 100k words named wordsEn.txt.
As an example, your spell checker should correct the following mistakes.
comlete -> complete (case a)
deciasion -> decision (case b)
lwa -> law (case c)
Correct any word that does not exist in the dictionary file provided, (even if it is correct in
the English language).
Some hints:
1. Note that the dictionary we provide is a subset of the actual English dictionary, as
long as your spell check is logical you will get the grade. For instance, the letter “i”
is not in the dictionary and the correction could be “in”, “if” or even “hi”. This is an
acceptable output.
2. Also, if “Editor’s” is corrected to “editors” that is ok. (case B, remove character)
3. We suggest all punctuation at the beginning and end be removed and for all words
convert the letters to lower case (for e.g. Hello! is replaced with hello, before the
spell checking itself).
Do NOT write any functionality inside the main() function within spell_check.cc. Write
all functionality inside the testSpellingWrapper() within that file. We will be using our
own main, directly calling testSpellingWrapper(). This wrapper function is passed all
the command line arguments as you would normally have in a main.
You will print the word, whether it is already spelled correctly (aka found), and all the
possible spelling corrections if the word is not found in the dictionary. Be wary of
punctuation and formatting in the document when parsing!
Exact deliverables and output format are described below.
DELIVERABLES
You should submit these files:
1. README    file
2. create_and_test_hash.cc (modified)
3. spell_check.cc (modified)
4. linear_probing.h (new)
5. quadratic_probing.h (modified)
6. double_hashing.h (new)