Buy/Download all MCQ Ebook >>>Click Here<<<
Rabin-Karp Algorithm Multiple choice Questions and Answers (MCQs)
Click on any option to know the CORRECT ANSWERS
Question 1 |
What is a Rabin and Karp Algorithm?
String Matching Algorithm | |
Shortest Path Algorithm | |
Minimum spanning tree Algorithm | |
Approximation Algorithm |
Question 1 Explanation:
The string matching algorithm which was proposed by Rabin and Karp, generalizes to other algorithms and for two-dimensional pattern matching problems.
Question 2 |
What is the pre-processing time of Rabin and Karp Algorithm?
Theta(m2) | |
Theta(mlogn) | |
Theta(m) | |
Big-Oh(n) |
Question 2 Explanation:
The for loop in the pre-processing algorithm runs for m(length of the pattern) times. Hence the pre-processing time is Theta(m).
Question 3 |
Rabin Karp Algorithm makes use of elementary number theoretic notions.
True | |
False |
Question 3 Explanation:
Rabin Karp Algorithm makes use of elementary theoretic number notions such as the equivalence of two numbers modulo a third number.
Question 4 |
What is the basic formula applied in Rabin Karp Algorithm to get the computation time as Theta(m)?
Halving rule | |
Horner's rule | |
Summation lemma | |
Cancellation lemma |
Question 4 Explanation:
The pattern can be evaluated in time Theta(m) using Horner's rule:
p = P[m] + 10(P[m-1] + 10(P[m-2] +...+ 10(P[2]+10P[1])...)).
Question 5 |
What is the worst case running time of Rabin Karp Algorithm?
Theta(n) | |
Theta(n-m) | |
Theta((n-m+1)m) | |
Theta(nlogm) |
Question 5 Explanation:
The worst case running time of Rabin Karp Algorithm is Theta(n-m+1)m). We write Theta(n-m+1) instead of Theta(n-m) because there are n-m+1 different values that the given text takes on.
There are 5 questions to complete.