Hashing Application

Analyzing Hashing Here you will experiment with the performance of linear probing hash tables to see if it matches the analysis given by the book. Implement linear probing and then run tests on the average number of probes required at various load factors using randomized input in order to obtain a graph like the one in Figure 5.12. Compare the values from this simulation to the closed form solution in the book/slides. You should use a fixed table size of 1009 (which is prime), do not rehash. For this assignment the results and your analysis are important. You will write a small 1-2 page report describing how you designed your experiment, a graph plotting the number of probes against the load factor, and a brief conclusion on how it compares to the book’s plot. Hashing Application Implement a spell checker by using the hash table with quadratic probing. Given a document your program should output all of the misspelled words. For each misspelled word you should also 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 each possible position b) Removing one character from the word c) Swapping adjacent characters in the word Your program should run as follows: spellcheck You will be provided with a small document named [login to view URL] and a dictionary file with approximately 100k words named wordsEn.txt. There is also a file named [login to view URL] that includes six misspelled words in [login to view URL] that your program should be able to correct. Note that there may be other words in the document that are not in the dictionary due to the limited size and scope of the dictionary. You do not have to correct those misspellings.