Download our App for Study Materials and Placement Preparation 📝✅ | Click Here 

([Link]

Get Latest Exam Updates, Free Study materials and Tips

Your Name
([Link]
Your Branch
[Link]/)
Year Of Engineering

[MCQ] Analysis Of Algorithms

Introduction (#1617622154105-59ec4c41-97a6)

Divide and Conquer Approach (#1617622154112-c1392ccd-f510)

Greedy Method Approach (#1617629753056-e13c69b7-cef6)

Dynamic Programming Approach (#1617632450818-4e763a5a-bfbe)

Backtracking and Branch and bound (#1617635582320-a3acc518-42aa)

String Matching Algorithms (#1617638004246-75673406-edcf)

 Module 6

1. What is a Rabin and Karp Algorithm?

a) String Matching Algorithm
b) Shortest Path Algorithm
c) Minimum spanning tree Algorithm
d) Approximation Algorithm
Answer: a
Explanation: The string matching algorithm which was proposed by Rabin and Karp, generalizes to other algorithms and for two-dimensional
pattern matching problems.

2. What is the pre-processing time of Rabin and Karp Algorithm?

a) Theta(m2)
b) Theta(mlogn)
c) Theta(m)
d) Big-Oh(n)
Answer: c
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).

3. Rabin Karp Algorithm makes use of elementary number theoretic notions.

a) True
b) False
Answer: a
Explanation: Rabin Karp Algorithm makes use of elementary theoretic number notions such as the equivalence of two numbers modulo a third
number.

4. 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
Answer: b
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])…)).

5. 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)
Answer: c
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.

6. Rabin- Karp algorithm can be used for discovering plagiarism in a sentence.

a) True
b) False
Answer: a
Explanation: Since Rabin-Karp algorithm is a pattern detecting algorithm in a text or string, it can be used for detecting plagiarism in a sentence.

7. If n is the length of text(T) and m is the length of the pattern(P) identify the correct pre-processing algorithm. (where q is a suitable
modulus to reduce the complexity)
p=0; t0=0;
a)

for i=1 to n
do t0=(dt0 + P[i])mod q
p=(dp+T[i])mod q
b)

for i=1 to n
do p=(dp + P[i])mod q
t0=(dt0+T[i])mod q
c)

for i=1 to m
do t0=(dp + P[i])mod q
p=(dt0+T[i])mod q
d)

for i=1 to m
do p=(dp + P[i])mod q
t0=(dt0+T[i])mod q
Answer: d
Explanation: The pre-processing algorithm runs m (the length of pattern) times. This algorithm is used to compute p as the value of P[1….m] mod
q and t0 as the value of T[1….m]mod q.

8. If n is the length of text(T) and m is the length of the pattern(P) identify the correct matching algorithm.
a)

for s=0 to n
do if p=t0
then if P[1..m]=T[s+1..s+m]
then print “Pattern occurs with shift” s
b)

for s=0 to n-m

do if p=ts
then if P[1..m]=T[s+1..s+m]
then print “Pattern occurs with shift” s
c)
for s=0 to m
do if p=ts
then if P[1..m]=T[s+1..s+m]
then print “Pattern occurs with shift” s
d)

for s=0 to n-m

do if p!=ts
then if P[1..m]=T[s+1..s+m]
then print “Pattern occurs with shift” s

Answer: b
Explanation: The matching algorithm runs for n-m times. Rabin Karp algorithm explicitly verifies every valid shift. If the required pattern matches
with the given text then the algorithm prints pattern found as result.

9. What happens when the modulo value(q) is taken large?

a) Complexity increases
b) Spurious hits occur frequently
c) Cost of extra checking is low
d) Matching time increases
Answer: c
Explanation: If the modulo value(q) is large enough then the spurious hits occur infrequently enough that the cost of extra checking is low.

10. Given a pattern of length-5 window, find the suitable modulo value.
43250
a) 13
b) 14
c) 12
d) 11
Answer: a
Explanation: The modulus q is typically chosen as a prime number that is large enough to reduce the complexity when p is very large.

Crack Job Placement Aptitude in First Attempt

Prepare for Aptitude with 50+ Videos Lectures and Handmade Notes
Click Here! ([Link]

11. Given a pattern of length- 5 window, find the valid match in the given text.
Pattern: 2 1 9 3 6
Modulus: 21
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Text: 9 2 7 2 1 8 3 0 5 7 1 2 1 2 1 9 3 6 2 3 9 7
a) 11-16
b) 3-8
c) 13-18
d) 15-20
Answer: c
Explanation: The pattern 2 1 9 3 6 occurs in the text starting from position 13 to 18. In the given pattern value is computed as 12 by having the
modulus as 21. The same text string values are computed for each possible position of a 5 length window.

12. Given a pattern of length- 5 window, find the spurious hit in the given text string.
Pattern: 3 1 4 1 5
Modulus: 13
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Text: 2 3 5 9 0 2 3 1 4 1 5 2 6 7 3 9 9 2 1 3 9
a) 6-10
b) 12-16
c) 3-7
d) 13-17
Answer: d
Explanation: The sub string in the range 13-17, 6 7 3 9 9 produces the same value 7 as the given pattern. But the pattern numbers don’t match with
sub string identified, hence it is a spurious hit.

13. If the expected number of valid shifts is small and modulus is larger than the length of pattern what is the matching time of Rabin
Karp Algorithm?
a) Theta(m)
b) Big-Oh(n+m)
c) Theta(n-m)
d) Big-Oh(n)
Answer: b
Explanation: When the number of valid shifts(v) is Big-Oh(1) and q>=m then the matching time is given by O(n)+O(m(v+n/q)) is simplified as
O(n+m).

14. What is the basic principle in Rabin Karp algorithm?

a) Hashing
b) Sorting
c) Augmenting
d) Dynamic Programming
Answer: a
Explanation: The basic principle employed in Rabin Karp algorithm is hashing. In the given text every substring is converted to a hash value and
compared with the hash value of the pattern.

15. Who created the Rabin Karp Algorithm?

a) Joseph Rabin and Michael Karp
b) Michael Rabin and Joseph Karp
c) Richard Karp and Michael Rabin
d) Michael Karp and Richard Rabin
Answer: c
Explanation: Rabin Karp algorithm was invented by Richard Karp and Michael Rabin in the year 1987 for searching a pattern in the given string.

Crack Job Placement Aptitude in First Attempt

Prepare for Aptitude with 50+ Videos Lectures and Handmade Notes
Click Here! ([Link]

16. Which of the following is the fastest algorithm in string matching field?
a) Boyer-Moore’s algorithm
b) String matching algorithm
c) Quick search algorithm
d) Linear search algorithm
Answer: c
Explanation: Quick search algorithm is the fastest algorithm in string matching field whereas Linear search algorithm searches for an element in an
array of elements.

17. Which of the following algorithms formed the basis for the Quick search algorithm?
a) Boyer-Moore’s algorithm
b) Parallel string matching algorithm
c) Binary Search algorithm
d) Linear Search algorithm
Answer: a
Explanation: Quick search algorithm was originally formed to overcome the drawbacks of Boyer-Moore’s algorithm and also for increased speed
and efficiency.

18. What is the time complexity of the Quick search algorithm?

a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)
Answer: c
Explanation: The time complexity of the Quick search algorithm was found to be O(m+n) and is proved to be faster than Boyer-Moore’s algorithm.
19. What character shift tables does quick search algorithm use?
a) good-character shift tables
b) bad-character shift tables
c) next-character shift tables
d) both good and bad character shift tables
Answer: b
Explanation: Quick search algorithm uses only bad character shift tables and it is one of the reasons for its increased speed than Boyer-Moore’s
algorithm.

20. What is the space complexity of quick search algorithm?

a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)
Answer: a
Explanation: The space complexity of quick search algorithm is mathematically found to be O(n) where n represents the input size.

Learn Machine Learning with Python from Scratch

Start your Machine learning & Data Science journey with Complete Hands-on Learning & doubt solving Support
Click Here! ([Link]

21. Quick search algorithm starts searching from the right most character to the left.
a) true
b) false
Answer: b
Explanation: Quick search algorithm starts searching from the left most character to the right and it uses only bad character shift tables.

22. What character shift tables does Boyer-Moore’s search algorithm use?
a) good-character shift tables
b) bad-character shift tables
c) next-character shift tables
d) both good and bad character shift tables
Answer: d
Explanation: Boyer-Moore’s search algorithm uses both good and bad character shift tables whereas quick search algorithm uses only bad character
shift tables.

23. What is the worst case running time in searching phase of Boyer-Moore’s algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)
Answer: d
Explanation: If the pattern occurs in the text, the worst case running time of Boyer-Moore’s algorithm is found to be O(mn).

24. The searching phase in quick search algorithm has good practical behaviour.
a) true
b) false
Answer: a
Explanation: During the searching phase, the comparison between pattern and text characters can be done in any order. It has a quadratic worst case
behaviour and good practical behaviour.

25. Given input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the first index of the pattern match using
quick search algorithm.
a) 2
b) 6
c) 11
d) 14
Answer: b
Explanation: By using quick search algorithm, the given input text string is preprocessed and starts its search from the left most character and finds
the first occurrence of the pattern at index=2.
 Python Programming for Complete Beginners

Start your Programming Journey with Python Programming which is Easy to Learn and Highly in Demand
Click Here! ([Link]

26. What will be the output of the following code?

#include<bits/stdc++.h>
using namespace std;

void func(char* str2, char* str1)

{
int m = strlen(str2);
int n = strlen(str1);
for (int i = 0; i <= n – m; i++)
{
int j;

for (j = 0; j < m; j++)

if (str1[i + j] != str2[j])
break;

if (j == m)
cout << i << endl;
}
}

int main()
{
char str1[] = “1253234”;
char str2[] = “323”;
func(str2, str1);
return 0;
}
a) 1
b) 2
c) 3
d) 4
Answer: c
Explanation: The given code describes the naive method of finding a pattern in a string. So the output will be 3 as the given sub string begins at that
index in the pattern.

27. What will be the worst case time complexity of the following code?
#include<bits/stdc++.h>
using namespace std;

void func(char* str2, char* str1)

{
int m = strlen(str2);
int n = strlen(str1);
for (int i = 0; i <= n – m; i++)
{
int j;

for (j = 0; j < m; j++)

if (str1[i + j] != str2[j])
break;

if (j == m)
cout << i << endl;
}
}
int main()
{
char str1[] = “1253234”;
char str2[] = “323”;
func(str2, str1);
return 0;
}
a) O(n)
b) O(m)
c) O(m * n)
d) O(m + n)
Answer: c
Explanation: The given code describes the naive method of pattern searching. By observing the nested loop in the code we can say that the time
complexity of the loop is O(m*n).

28. What will be the auxiliary space complexity of the following code?
#include<bits/stdc++.h>
using namespace std;

void func(char* str2, char* str1)

{
int m = strlen(str2);
int n = strlen(str1);
for (int i = 0; i <= n – m; i++)
{
int j;

for (j = 0; j < m; j++)

if (str1[i + j] != str2[j])
break;

if (j == m)
cout << i << endl;
}
}

int main()
{
char str1[] = “1253234”;
char str2[] = “323”;
func(str2, str1);
return 0;
}
a) O(n)
b) O(1)
c) O(log n)
d) O(m)
Answer: b
Explanation: The given code describes the naive method of pattern searching. Its auxiliary space requirement is O(1).

29. What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n)
b) O(n*m)
c) O(m)
d) O(log n)
Answer: c
Explanation: KMP algorithm is an efficient pattern searching algorithm. It has a time complexity of O(m) where m is the length of text.

30. What will be the best case time complexity of the following code?
#include<bits/stdc++.h>
using namespace std;
void func(char* str2, char* str1)
{
int m = strlen(str2);
int n = strlen(str1);

for (int i = 0; i <= n – m; i++)

{
int j;

for (j = 0; j < m; j++)

if (str1[i + j] != str2[j])
break;

if (j == m)
cout << i << endl;
}
}

int main()
{
char str1[] = “1253234”;
char str2[] = “323”;
func(str2, str1);
return 0;
}
a) O(n)
b) O(m)
c) O(m * n)
d) O(m + n)
Answer: b
Explanation: The given code describes the naive method of pattern searching. The best case of the code occurs when the first character of the
pattern does not appear in the text at all. So in such a case, only one iteration is required thus time complexity will be O(m).

Crack Job Placement Aptitude in First Attempt

Prepare for Aptitude with 50+ Videos Lectures and Handmade Notes
Click Here! ([Link]

31. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n + m)
b) O(m)
c) O(n)
d) O(m * n)
Answer: a
Explanation: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It has a time complexity of O(m + n)
where m is the length of text and n is the length of the pattern.

32. What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
a) O(n + m)
b) O(m)
c) O(n)
d) O(m * n)
Answer: b
Explanation: Z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. It an auxiliary space of O(m) for
maintaining Z array.

33. The naive pattern searching algorithm is an in place algorithm.

a) true
b) false
Answer: a
Explanation: The auxiliary space complexity required by naive pattern searching algorithm is O(1). So it qualifies as an in place algorithm.
 34. Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
a) true
b) false
Answer: a
Explanation: The worst case time complexity of Rabin Karp algorithm is O(m*n) but it has a linear average case time complexity. So Rabin Karp
and naive pattern searching algorithm have the same worst case time complexity.

35. The searching phase in quick search algorithm has good practical behaviour.
a. true
b. false
Answer a
true

36. If the expected number of valid shifts is small and modulus is larger than the length of pattern what is the matching time of Rabin
Karp Algorithm?
a. Theta(m)
b. Big-Oh(n+m)
c. Theta(n-m)
d. Big-Oh(n)
Answer d

Big-Oh(n+m)

Learn Machine Learning with Python from Scratch

Start your Machine learning & Data Science journey with Complete Hands-on Learning & doubt solving Support
Click Here! ([Link]

Prepare For Your Placements: [Link] ([Link]

preparation/)
([Link]

included-mentorship/youtube-2/)

/ Youtube Channel: [Link]

([Link]

Follow For Latest Updates, Study Tips & More Content!

([Link]
included-mentorship/insta-1/)/lastmomenttuition ([Link]

([Link]
included-mentorship/link/)/ Last Moment Tuitions ([Link]
tuitions#:~:text=Last%20Moment%20Tuitions%20(LMT)%20is,others%20is%20its%20teaching%20methodology.)

([Link]
included-mentorship/twittrwer/)/ lastmomentdost ([Link]