7 practice sets · Page 1 of 1
Which of the following is the longest common subsequence between the strings "hbcfgmnapq" and "cbhgrsfnmq" ?
hgmq
cfnq
bfmq
fgmna
Correct Answer: D — fgmna
Explanation:
The length of the longest common subsequence is 4. But 'fgmna' is not the longest common subsequence as its length is 5.
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].
Correct Answer: B — arr[i][j] = 1 + arr[i - 1][j - 1].
Explanation:
The line, arr[i][j] = 1 + arr[i - 1][j - 1] completes the above code.
What is the time complexity of the brute force algorithm used to find the longest common subsequence?
O(n)
O(n^{2})
O(n^{3})
O(2^{n})
Correct Answer: D — O(2^{n})
Explanation:
The time complexity of the brute force algorithm used to find the longest common subsequence is O(2^{n}).
Longest common subsequence is an example of ____________
Greedy algorithm
2D dynamic programming
1D dynamic programming
Divide and conquer
Correct Answer: B — 2D dynamic programming
Explanation:
Longest common subsequence is an example of 2D dynamic programming.
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
Correct Answer: B — Longest palindromic subsequence
Explanation:
To find the longest palindromic subsequence in a given string, reverse the given string and then find the longest common subsequence in the given string and the reversed string.
Consider the strings "PQRSTPQRS" and "PRATPBRQRPS". What is the length of the longest common subsequence?
9
8
7
6
Correct Answer: C — 7
Explanation:
The longest common subsequence is "PRTPQRS" and its length is 7.
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
Correct Answer: C — Both recursion and dynamic programming
Explanation:
Both recursion and dynamic programming can be used to solve the longest subsequence problem.
