hashing that the first starts at number and each statement has number higher than the previous statement you may assume an upper limit of statementsbut the statement numbers in the input might be as large as -bit integer your program must run in linear time implement the word puzzle program using the algorithm described at the end of the we can get big speed increase by storingin addition to each word wall of ' prefixes (if one of ' prefixes is another word in the dictionaryit is stored as real word although this may seem to increase the size of the hash table drasticallyit does notbecause many words have the same prefixes when scan is performed in particular directionif the word that is looked up is not even in the hash table as prefixthen the scan in that direction can be terminated early use this idea to write an improved program to solve the word puzzle if we are willing to sacrifice the sanctity of the hash table adtwe can speed up the program in part (bby noting that iffor examplewe have just computed the hash function for "excel,we do not need to compute the hash function for "excelsfrom scratch adjust your hash function so that it can take advantage of its previous calculation in we suggested using binary search incorporate the idea of using prefixes into your binary search algorithm the modification should be simple which algorithm is fasterunder certain assumptionsthe expected cost of an insertion into hash table with secondary clustering is given by /( - )- -ln( -lunfortunatelythis formula is not accurate for quadratic probing howeverassuming that it isdetermine the followinga the expected cost of an unsuccessful search the expected cost of successful search implement generic map that supports the insert and lookup operations the implementation will store hash table of pairs (keydefinitionyou will lookup definition by providing key figure provides the map specification (minus some details implement spelling checker by using hash table assume that the dictionary comes from two sourcesan existing large dictionary and second file containing personal dictionary output all misspelled words and the line numbers on which they occur alsofor each misspelled wordlist any words in the dictionary that are obtainable by applying any of the following rulesa add one character remove one character exchange adjacent characters prove markov' inequalityif is any random variable and then pr| > < | )/ show how this inequality can be applied to theorems and if hopscotch table with parameter max_dist has load factor what is the approximate probability that an insertion requires rehash