ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
20 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
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
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)
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
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
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)
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
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
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)
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
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.
Given input string = "ABCDABCATRYCARCABCSRT" and pattern string = "CAT". Find the first index of the pattern match using Quick search algorithm.
2
6
11
14
Using Quick search algorithm, searching starts from the leftmost character and finds the first occurrence of the pattern "CAT" at index 6.
The searching phase in Quick search algorithm has good practical behaviour.
True
False
During the searching phase, comparisons can be done in any order. It has quadratic worst-case behaviour but good practical behaviour.
What is the worst case running time in the searching phase of Boyer-Moore's algorithm?
O(n)
O(log n)
O(m+n)
O(mn)
If the pattern occurs in the text, the worst case running time of Boyer-Moore's algorithm is O(mn).
What character shift tables does Boyer-Moore's search algorithm use?
Good-character shift tables
Bad-character shift tables
Next-character shift tables
Both good and bad character shift tables
Boyer-Moore's algorithm uses both good-character and bad-character shift tables, whereas Quick search uses only bad-character shift tables.
Quick search algorithm starts searching from the rightmost character to the left.
True
False
Quick search algorithm starts searching from the leftmost character to the right, and uses only bad-character shift tables.
What is the space complexity of the Quick search algorithm?
O(n)
O(log n)
O(m+n)
O(mn)
The space complexity of the Quick search algorithm is O(n), where n represents the input size.
What character shift tables does the Quick search algorithm use?
Good-character shift tables
Bad-character shift tables
Next-character shift tables
Both good and bad character shift tables
Quick search algorithm uses only bad-character shift tables, which is one of the reasons for its increased speed over Boyer-Moore's algorithm.
What is the time complexity of the Quick search algorithm?
O(n)
O(log n)
O(m+n)
O(mn)
The time complexity of the Quick search algorithm is O(m+n), which is proven to be faster than Boyer-Moore's algorithm.
Which of the following algorithms formed the basis for the Quick search algorithm?
Boyer-Moore's algorithm
Parallel string matching algorithm
Binary search algorithm
Linear search algorithm
Quick search algorithm was developed to overcome the drawbacks of Boyer-Moore's algorithm, improving speed and efficiency.
Which of the following is the fastest algorithm in the string matching field?
Boyer-Moore's algorithm
String matching algorithm
Quick search algorithm
Linear search algorithm
Quick search algorithm is the fastest algorithm in the string matching field, whereas linear search searches for an element in an array sequentially.
