mod tablesize (section describes method of performing this calculation without overflowsbut it is unlikely that overflow matters in this case explain why this strategy tends to avoid secondary clusteringand compare this strategy with both double hashing and quadratic probing rehashing requires recomputing the hash function for all items in the hash table since computing the hash function is expensivesuppose objects provide hash member function of their ownand each object stores the result in an additional data member the first time the hash function is computed for it show how such scheme would apply for the employee class in figure and explain under what circumstances the remembered hash value remains valid in each employee write program to implement the following strategy for multiplying two sparse polynomials of size and nrespectively each polynomial is represented as list of objects consisting of coefficient and an exponent we multiply each term in by term in for total of mn operations one method is to sort these terms and combine like termsbut this requires sorting mn recordswhich could be expensiveespecially in small-memory environments alternativelywe could merge terms as they are computed and then sort the result write program to implement the alternative strategy if the output polynomial has about ( ntermswhat is the running time of both methods describe procedure that avoids initializing hash table (at the expense of memory suppose we want to find the first occurrence of string pk in long input string an we can solve this problem by hashing the pattern stringobtaining hash value hp and comparing this value with the hash value formed from ak ak+ ak+ and so on until an- + an- + an if we have match of hash valueswe compare the strings character by character to verify the match we return the position (in aif the strings actually do matchand we continue in the unlikely event that the match is false show that if the hash value of + ai+ - is knownthen the hash value of ai+ ai+ ai+ can be computed in constant time show that the running time is ( nplus the time spent refuting false matches show that the expected number of false matches is negligible write program to implement this algorithm describe an algorithm that runs in ( nworst-case time  describe an algorithm that runs in ( /kaverage time nonstandard +extension adds syntax that allows switch statement to work with the string type (instead of the primitive integer typesexplain how hash tables can be used by the compiler to implement this language addition an (old-stylebasic program consists of series of statements numbered in ascending order control is passed by use of goto or gosub and statement number write program that reads in legal basic program and renumbers the statements so