Rabin-Karp Algorithm Multiple choice Questions and Answers (MCQs)

DOWNLOAD FREE PDF <<CLICK HERE>>

Rabin-Karp Algorithm Multiple choice Questions and Answers (MCQs)

Congratulations - you have completed Rabin-Karp Algorithm Multiple choice Questions and Answers (MCQs).

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%


Your answers are highlighted below.
Question 1 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
What is a Rabin and Karp Algorithm?
A
String Matching Algorithm
B
Shortest Path Algorithm
C
Minimum spanning tree Algorithm
D
Approximation Algorithm

CLICK HERE FOR ALL SUBJECTS MCQ

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 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
What is the pre-processing time of Rabin and Karp Algorithm?
A
Theta(m2)
B
Theta(mlogn)
C
Theta(m)
D
Big-Oh(n)

CLICK HERE FOR ALL SUBJECTS MCQ

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 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Rabin Karp Algorithm makes use of elementary number theoretic notions.
A
True
B
False

CLICK HERE FOR ALL SUBJECTS MCQ

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 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
What is the basic formula applied in Rabin Karp Algorithm to get the computation time as Theta(m)?
A
Halving rule
B
Horner's rule
C
Summation lemma
D
Cancellation lemma

CLICK HERE FOR ALL SUBJECTS MCQ

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 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
What is the worst case running time of Rabin Karp Algorithm?
A
Theta(n)
B
Theta(n-m)
C
Theta((n-m+1)m)
D
Theta(nlogm)

CLICK HERE FOR ALL SUBJECTS MCQ

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.

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results
There are 5 questions to complete.

DOWNLOAD FREE PDF <<CLICK HERE>>