ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?
O(1)
O(2^{n})
O(n)
O(n^{2})
In the brute force algorithm, all the subsequences are found and the length of the longest palindromic subsequence is calculated. This takes exponential time.
What is the length of the longest palindromic subsequence for the string "ababcdabba"?
6
7
8
9
The longest palindromic subsequence is "abbabba" and its length is 7.
For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence?
A string that is a palindrome
A string of length one
A string that has all the same letters(e.g. aaaaaa)
Some strings of length two
A string of length 2 for eg: ab is not a palindrome.
Which of the following is not a palindromic subsequence of the string "ababcdabba"?
abcba
abba
abbbba
adba
'adba' is not a palindromic sequence.
Which of the following methods can be used to solve the longest palindromic subsequence problem?
Dynamic programming
Recursion
Brute force
Dynamic programming, Recursion, Brute force
Dynamic programming, Recursion, Brute force can be used to solve the longest palindromic subsequence problem.
In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?
O(n)
O(n^{2})
O(n!)
O(2^{n})
The time required to find all the subsequences of a given sequence is 2^{n}, where 'n' is the number of elements in the sequence. So, the time complexity is O(2^{n}).
The number of increasing subsequences with the longest length for the given sequence are: {10, 9, 8, 7, 6, 5}
3
4
5
6
Each array element individually forms a longest increasing subsequence and so, the length of the longest increasing subsequence is 1. So, the number of increasing subsequences with the longest length is 6.
For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
True
False
For a given sequence, it is possible that there is more than one subsequence with the longest length.
Consider, the following sequence: {10,11,12,1,2,3}:
There are two longest increasing subsequences: {1,2,3} and {10,11,12}.
Find the length of the longest increasing subsequence for the given sequence: {-10, 24, -9, 35, -21, 55, -41, 76, 84}
5
4
3
6
The longest increasing subsequence is {-10, 24, 35, 55, 76, 84} and it's length is 6.
Find the longest increasing subsequence for the given sequence: {10, -10, 12, 9, 10, 15, 13, 14}
{10, 12, 15}
{10, 12, 13, 14}
{-10, 12, 13, 14}
{-10, 9, 10, 13, 14}
The longest increasing subsequence is {-10, 9, 10, 13, 14}.
The longest increasing subsequence problem is a problem to find the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and it's length is maximum. This problem can be solved using __________
Recursion
Dynamic programming
Brute force
Recursion, Dynamic programming, Brute force
The longest increasing subsequence problem can be solved using all of the mentioned methods.
Which of the following is the longest common subsequence between the strings "hbcfgmnapq" and "cbhgrsfnmq" ?
hgmq
cfnq
bfmq
fgmna
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].
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})
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
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
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
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
Both recursion and dynamic programming can be used to solve the longest subsequence problem.
What is the space complexity of Kadane's algorithm?
O(1)
O(n)
O(n^{2})
None of the mentioned
Kadane's algorithm uses a constant space. So, the space complexity is O(1).
