Algorithm MCQs

1. What is the worst-case time complexity of the Naive String Matching algorithm?

a)O(n) b)O(m) c)O((n-m+1)m) d)O(nlog m)

2. Which algorithm uses a rolling hash function to improve the average-case performance of string matching?

a) Naive Algorithm b) Rabin-Karp Algorithm c) Knuth-Morris-Pratt Algorithm d) Boyer-Moore Algorithm

3. What is the worst-case time complexity of the Knuth-Morris-Pratt (KMP) algorithm?

a)O(n) b)O(m) c)O(n + m) d)O(nlog m)

4. What is the purpose of the prefix function Pi in the KMP algorithm?

a) To compute the hash value of the pattern b) To avoid unnecessary comparisons by using information from previous matches c) To sort the characters of the pattern d) To divide the pattern into smaller substrings

5. Which of the following is true about the Rabin-Karp Algorithm?

a) It always performs better than the Naive Algorithm. b) It uses a prefix function to avoid unnecessary comparisons. c) It has a worst-case time complexity of O(n + m). d) It uses a rolling hash function to compare substrings.

6. What is the main advantage of the KMP algorithm over the Naive Algorithm?

a) It has a lower worst-case time complexity. b) It does not require preprocessing. c) It uses less memory. d) It is easier to implement.

7. In the Rabin-Karp Algorithm, what is the purpose of reducing the hash value modulo q ?

a) To ensure the hash value is always positive b) To handle large hash values and avoid overflow c) To sort the characters of the pattern d) To divide the pattern into smaller substrings

8. What is the time complexity of computing the prefix function Pi in the KMP algorithm?

a)O(n) b)O(m) c)O(n + m) d)O(nlog m)

9. Which of the following is a spurious hit in the Rabin-Karp Algorithm?

a) A match where the hash values are equal but the substrings are not. b) A match where the hash values are not equal but the substrings are. c) A match where the pattern is found at the beginning of the text. d) A match where the pattern is found at the end of the text.

10. What is the key idea behind the KMP algorithm?

a) It uses a rolling hash function to compare substrings. b) It avoids backtracking on the text by using a prefix function. c) It sorts the characters of the pattern before matching. d) It divides the text into smaller substrings for parallel processing.

11. What is the primary disadvantage of the Naive String Matching algorithm?

a) It requires extra memory. b) It has a high worst-case time complexity. c) It cannot handle patterns with repeated characters. d) It only works for binary strings.

12. In the Rabin-Karp Algorithm, what is the purpose of the rolling hash function?

a) To sort the characters of the pattern. b) To compute the hash value of the pattern and substrings efficiently. c) To divide the text into smaller substrings. d) To avoid backtracking on the text.

13. What is the role of the modulus q in the Rabin-Karp Algorithm?

a) To ensure the hash value is always positive. b) To reduce the size of the hash value and avoid overflow. c) To sort the characters of the pattern. d) To divide the text into smaller substrings.

14. Which of the following is true about the KMP algorithm?

a) It requires backtracking on the text. b) It has a worst-case time complexity of O(n^2). c) It uses a prefix function to avoid unnecessary comparisons. d) It cannot handle patterns with repeated characters.

15. What is the time complexity of the Rabin-Karp Algorithm in the worst case?

a)O(n) b)O(m) c)O(n + m) d)O((n-m+1)m)

16. What is the purpose of the prefix function Pi in the KMP algorithm?

a) To compute the hash value of the pattern. b) To determine the longest prefix of the pattern that is also a suffix of the current substring. c) To sort the characters of the pattern. d) To divide the text into smaller substrings.

17. Which of the following is true about the Rabin-Karp Algorithm?

a) It always performs better than the KMP algorithm. b) It has a preprocessing step that takes \( O(m) \) time. c) It cannot handle patterns with repeated characters. d) It uses a rolling hash function to compare substrings.

18. What is the time complexity of the KMP algorithm's matching phase?

a)O(n) b)O(m) c)O(n + m) d)O(nlog m)

19. Which of the following is a key advantage of the Rabin-Karp Algorithm over the Naive Algorithm?

a) It has a lower worst-case time complexity. b) It uses less memory. c) It can handle patterns with repeated characters. d) It has better average-case performance.

20. What is the purpose of the prefix function Pi in the KMP algorithm?

a) To compute the hash value of the pattern. b) To avoid backtracking on the text by using information from previous matches. c) To sort the characters of the pattern. d) To divide the text into smaller substrings.

String Matching Algorithms MCQs

Your Score: /20