2. A spelling checker program reads an input file and prints all the words not found in some on-line dictionary. Suppose the dictionary contains 20,000 words and the input file is large, so that the algorithm can make only one pass through the input file. A simple strategy is to read the dictionary into a hash table and look for each input word as it is read. (a) Assuming that an average word is 7 characters long and that it is possible to store words of L characters in L +1 bytes (so space wastage is not a consideration), and assuming a quadratic probing hash table, how much space does the table require? (b) If memory is limited and the entire dictionary cannot be stored in a hash table, we can still get an efficient algorithm that almost always works. We declare a table of boolean (initialized to false) from 0 to Tablesize -1. As we read in a word, we set table [hash (word)] true. Which of the following is true? i. If a word hashes to a location with value that is false, the word is not in the dictionary ii. If a word hashes to a location with value that is true, the word is in the dictionary. 111. Suppose we choose Tables ize = 200,007 How much memory does this require? iv. What is the probability of an error in this scheme? 2. A spelling checker program reads an input file and prints all the words not found in some on-line dictionary. Suppose the dictionary contains 20,000 words and the input file is large, so that the algorithm can make only one pass through the input file. A simple strategy is to read the dictionary into a hash table and look for each input word as it is read. (a) Assuming that an average word is 7 characters long and that it is possible to store words of L characters in L +1 bytes (so space wastage is not a consideration), and assuming a quadratic probing hash table, how much space does the table require? (b) If memory is limited and the entire dictionary cannot be stored in a hash table, we can still get an efficient algorithm that almost always works. We declare a table of boolean (initialized to false) from 0 to Tablesize -1. As we read in a word, we set table [hash (word)] true. Which of the following is true? i. If a word hashes to a location with value that is false, the word is not in the dictionary ii. If a word hashes to a location with value that is true, the word is in the dictionary. 111. Suppose we choose Tables ize = 200,007 How much memory does this require? iv. What is the probability of an error in this scheme