Unit 2: String Matching Algorithms and Computational Geometry - Practice Quiz

1 How does sequential search look for a target element in a list?

2 What is the worst-case time complexity of sequential search on a list of elements?

3 What does brute-force string matching do at each possible position in the text?

4 For a text of length and a pattern of length , how many possible alignments are checked by brute-force matching?

5 After a mismatch, how far does the naive pattern-matching algorithm normally shift the pattern?

6 Which preprocessing step is required by the basic naive pattern-matching algorithm?

7 Which technique is central to the Rabin-Karp string-matching algorithm?

8 What should Rabin-Karp do when a text window and the pattern have the same hash value?

9 What is a hash collision in Rabin-Karp?

10 Which table is constructed during preprocessing in the KMP algorithm?

11 What does LPS stand for in the KMP algorithm?

12 What is the time complexity of KMP for a text of length and a pattern of length ?

13 What does a suffix array store?

14 Which data structure stores characters in indexed, contiguous positions and allows direct character access?

15 What do paths from the root of a trie represent?

16 Which operation is a trie especially useful for?

17 What is the goal of the closest-pair problem?

18 What is the time complexity of checking every pair among points?

19 What is the convex hull of a set of points?

20 Which everyday analogy commonly describes a convex hull?

21 A sequential search is performed on the array [14, 8, 23, 5, 11, 19] to find the key 11. How many element comparisons are made?

22 A key is known to be present in an unsorted array of elements, and every position is equally likely to contain it. What is the expected number of comparisons made by sequential search?

23 Using brute-force string matching, how many character comparisons are made when searching for pattern aaa in text aaaaa, assuming all possible alignments are checked?

24 For a text of length and a pattern of length , which expression gives the worst-case number of character comparisons in brute-force string matching?

25 Using 0-based indexing, at which positions does the naive pattern-matching algorithm find pattern ABA in text ABABA?

26 The naive algorithm searches for pattern AAB in text AAAAAB. How many character comparisons are performed before the match is found?

27 In Rabin-Karp, decimal digits are hashed using base and modulus . The current window 26 has hash 4. After sliding to window 63, what is the new hash?

28 During Rabin-Karp matching, a text window and the pattern have equal hash values. What should the algorithm do next?

29 What is the worst-case time complexity of Rabin-Karp when many text windows have the same hash as the pattern?

30 What is the LPS array for the pattern ABABCABAB?

31 KMP has matched the first five characters ABABA of pattern ABABAC. The next text character causes a mismatch with C. To what matched-prefix length does KMP first fall back?

32 Using 0-based indexing, which starting positions will KMP report when searching for pattern AAA in text AAAAA?

33 What is the suffix array of the string banana, represented as the starting indices of suffixes in lexicographic order?

34 A suffix array for a text of length has already been built. If comparing a pattern of length with a suffix costs , what is the basic binary-search time for finding the pattern?

35 How many nodes are required to store the words cat, car, and dog in a standard trie, including the root and assuming end-of-word markers are not separate nodes?

36 A trie stores many words and keeps a word-count value at every node. What is the time complexity of counting words beginning with a prefix of length ?

37 Which pair is closest among the points , , , and ?

38 What is the time complexity of the divide-and-conquer closest-pair algorithm when points are maintained in sorted order during recursion?

39 For points , , and , what orientation does the ordered triplet have?

40 Consider the points , , , , and . Which sequence gives the convex hull in counterclockwise order starting from ?

41 An array of length contains exactly occurrences of a target. Their positions are chosen uniformly from all -element subsets of . Sequential search stops at the first occurrence. What is the expected number of inspected elements?

42 Four distinct keys have successful-search probabilities , respectively; an unsuccessful search has probability . A failed sequential search examines all four keys. Which ordering minimizes the expected number of comparisons, and what is that expectation?

43 A brute-force matcher compares characters left to right and stops an alignment at its first mismatch. For and , how many character comparisons are performed over all possible alignments?

44 For text length and pattern searched in , what exact number of character comparisons does left-to-right brute-force matching perform?

45 The naive matcher tests every alignment, compares left to right, and stops on the first mismatch. For and , how many total character comparisons are made, including successful alignments?

46 Rabin-Karp uses radix , modulus , and window length . The current window is , whose hash is . After shifting to the window , what hash is obtained using the rolling-hash update?

47 Using radix and modulus , Rabin-Karp searches for the two-digit pattern in . How many hash hits occur, and how many of them are spurious?

48 A Rabin-Karp implementation verifies every hash hit character by character. Which worst-case running time remains possible for a single pattern of length in a text of length ?

49 Using zero-based indexing, what is the KMP prefix-function array for the pattern ?

50 For , KMP is in state , meaning that has been matched. If the next text character is , what state is reached after all necessary fallback transitions?

51 KMP searches for in and must report overlapping matches. Which starting positions are reported, and to which state should it fall back immediately after each complete match?

52 For the string , the LCP values between lexicographically adjacent suffixes are . How many distinct nonempty substrings does contain?

53 A suffix array for a text of length is searched for a pattern of length using two ordinary binary searches, without LCP acceleration. If occurrences are reported, what is the worst-case query time?

54 A standard trie stores terminal status as a flag rather than as a separate node. After inserting , how many nodes does the trie contain, including the root?

55 A compacted trie stores prefix-free keys and suppresses every nonroot internal node of degree one. What is the maximum possible total number of nodes?

56 In the planar divide-and-conquer closest-pair algorithm, let be the smaller recursive distance. Candidate strip points are processed in increasing -order. Under the standard packing argument, how many subsequent strip points must each point be compared with at most?

57 A divide-and-conquer closest-pair implementation correctly divides by but re-sorts the points in each recursive subproblem by , costing per recursion level. What overall recurrence and running time result?

58 For the point set , which sequence lists exactly the convex-hull vertices in counterclockwise order, starting at ?

59 In Graham scan, several points have the same polar angle from the pivot. If the desired hull excludes nonvertex points lying along an edge, which tie treatment is correct?

60 In Jarvis march, multiple points may be collinear in the most counterclockwise direction from the current hull vertex. Which rule and complexity statement are correct for a hull with vertices?