the authors provide several ideas on possible further improvements one is to combine the strategy explained abovewhich provides greater shifting steps when mismatch is presentwith the knuth-morrispratt strategywhich allows larger shifts after detection of (partialmatch this method requires two precomputed tablesd is the table used aboveand is the table corresponding to the one of the kmpalgorithm the step taken is then the larger of the twoboth indicating that no smaller step could possibly lead to match we refrain from further elaborating the subjectbecause the additional complexity of the table generation and the search itself does not seem to yield any appreciable efficiency gain in factthe additional overhead is largerand casts some uncertainty whether the sophisticated extension is an improvement or deterioration exercises assume that the cardinalities of the standard types integerreal and char are denoted by intc real and char what are the cardinalities of the following data types defined as exemples in this complexdatepersonrowcardname which are the instruction sequences (on your computerfor the following(afetch and store operations for an element of packed records and arrays(bset operationsincluding the test for membership what are the reasons for defining certain sets of data as sequences instead of arrays given is railway timetable listing the daily services on several lines of railway system find representation of these data in terms of arraysrecordsor sequenceswhich is suitable for lookup of arrival and departure timesgiven certain station and desired direction of the train given text in the form of sequence and lists of small number of words in the form of two arrays and assume that words are short arrays of characters of small and fixed maximum length write program that transforms the text into text by replacing each occurrence of word ai by its corresponding word bi compare the following three versions of the binary search with the one presented in the text which of the three programs are correctdetermine the relevant invariants which versions are more efficientwe assume the following variablesand the constant var ijkxintegeraarray of integerprogram ai : : - repeat :( +jdiv if [kx then : else : end until ( [kxor ( jprogram bi : : - repeat :( +jdiv if [kthen : - endif [kx then : + end until