2. A spelling checker program reads an input file and prints al 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 Ta esize-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. iii. Suppose we choose Tablesize-200,007 How much memory does this require? iv. What is the probability of an error in this scheme