Longest Common Subsequence Quiz
Authored by Nancy P
Computers
University
Used 4+ times
AI Actions
Add similar questions
Adjust reading levels
Convert to real-world scenario
Translate activity
More...
Content View
Student View
8 questions
Show all answers
1.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Which of the following methods can be used to solve the longest common subsequence problem?
Recursion
Dynamic programming
Both recursion and dynamic programming
Greedy algorithm
2.
MULTIPLE CHOICE QUESTION
30 sec • 3 pts
Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?
9
8
7
6
3.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Which of the following problems can be solved using the longest subsequence problem?
Longest increasing subsequence
Longest palindromic subsequence
Longest bitonic subsequence
Longest decreasing subsequence
4.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Longest common subsequence is an example of ____________
Greedy algorithm
2D dynamic programming
1D dynamic programming
Divide and conquer
5.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
What is the time complexity of the brute force algorithm used to find the longest common subsequence?
O(n)
O(n2)
O(n3)
O(2^n)
6.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
Consider the following dynamic programming implementation of the longest common subsequence problem: for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { if(str1[i-1] == str2[j - 1]) ______________; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } Which of the following lines completes the above code?
arr[i][j] = 1 + arr[i][j].
arr[i][j] = 1 + arr[i – 1][j – 1].
arr[i][j] = arr[i – 1][j – 1].
arr[i][j] = arr[i][j].
7.
MULTIPLE CHOICE QUESTION
30 sec • 1 pt
What is the time complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?
O(n)
O(m)
O(m + n)
O(mn)
Access all questions and much more by creating a free account
Create resources
Host any resource
Get auto-graded reports
Continue with Google
Continue with Email
Continue with Microsoft
or continue with
%20(1).png)
Apple
Others
By signing up, you agree to our Terms of Service & Privacy Policy
Already have an account?
