10 practice sets · Page 1 of 1
Who created the Rabin-Karp Algorithm?
Joseph Rabin and Michael Karp
Michael Rabin and Joseph Karp
Richard Karp and Michael Rabin
Michael Karp and Richard Rabin
Correct Answer: C — Richard Karp and Michael Rabin
Explanation:
Rabin-Karp algorithm was invented by Richard Karp and Michael Rabin in 1987 for pattern searching in strings.
What is the basic principle in the Rabin-Karp algorithm?
Hashing
Sorting
Augmenting
Dynamic programming
Correct Answer: A — Hashing
Explanation:
Rabin-Karp uses hashing. Every substring of the text is converted to a hash value and compared with the hash value of the pattern for fast matching.
If the expected number of valid shifts is small and modulus is larger than the pattern length, what is the matching time of the Rabin-Karp Algorithm?
Theta(m)
O(n+m)
Theta(n-m)
O(n)
Correct Answer: B — O(n+m)
Explanation:
When the number of valid shifts v is O(1) and q >= m, the matching time O(n) + O(m(v + n/q)) simplifies to O(n+m).
What happens when the modulo value (q) is taken large?
Complexity increases
Spurious hits occur frequently
Cost of extra checking is low
Matching time increases
Correct Answer: C — Cost of extra checking is low
Explanation:
If q is large enough, spurious hits occur infrequently, making the cost of extra checking low.
Rabin-Karp algorithm can be used for discovering plagiarism in a sentence.
True
False
Correct Answer: A — True
Explanation:
Since Rabin-Karp is a pattern detection algorithm, it can be applied to detect plagiarism by searching for matching text patterns across documents.
What is the worst case running time of the Rabin-Karp Algorithm?
Theta(n)
Theta(n-m)
Theta((n-m+1)m)
Theta(n log m)
Correct Answer: C — Theta((n-m+1)m)
Explanation:
The worst case running time is Theta((n-m+1)m). We write n-m+1 instead of n-m because there are n-m+1 different positions the pattern can start in the text.
What is the basic formula applied in Rabin-Karp Algorithm to achieve pre-processing in Theta(m)?
Halving rule
Horner's rule
Summation lemma
Cancellation lemma
Correct Answer: B — Horner's rule
Explanation:
Horner's rule is used to evaluate the pattern in Theta(m): p = P[m] + 10(P[m-1] + 10(P[m-2] + ... + 10(P[2] + 10P[1])...)).
Rabin-Karp Algorithm makes use of elementary number theoretic notions.
True
False
Correct Answer: A — True
Explanation:
Rabin-Karp Algorithm uses elementary number theoretic notions such as the equivalence of two numbers modulo a third number.
What is the pre-processing time of the Rabin-Karp Algorithm?
Theta(m^2)
Theta(m log n)
Theta(m)
O(n)
Correct Answer: C — Theta(m)
Explanation:
The for loop in the pre-processing step runs m times (length of the pattern). Hence the pre-processing time is Theta(m).
What is the Rabin-Karp Algorithm?
String matching algorithm
Shortest path algorithm
Minimum spanning tree algorithm
Approximation algorithm
Correct Answer: A — String matching algorithm
Explanation:
Rabin-Karp is a string matching algorithm proposed by Rabin and Karp. It generalizes to other algorithms and also applies to two-dimensional pattern matching problems.
