Browse topic-based Data Structure And Algorithm practice sets.
302 practice sets · Page 8 of 16
For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
True
False
Correct Answer: B — False
Explanation:
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
Correct Answer: D — 6
Explanation:
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}
Correct Answer: D — {-10, 9, 10, 13, 14}
Explanation:
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
Correct Answer: D — Recursion, Dynamic programming, Brute force
Explanation:
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
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.
What is the space complexity of Kadane's algorithm?
O(1)
O(n)
O(n^{2})
None of the mentioned
Correct Answer: A — O(1)
Explanation:
Kadane's algorithm uses a constant space. So, the space complexity is O(1).
What is the time complexity of Kadane's algorithm?
O(1)
O(n)
O(n^{2})
O(5)
Correct Answer: B — O(n)
Explanation:
The time complexity of Kadane's algorithm is O(n) because there is only one for loop which scans the entire array exactly once.
For which of the following inputs would Kadane's algorithm produce a WRONG output?
{1,0,-1}
{-1,-2,-3}
{1,2,3}
{0,0,0}
Correct Answer: B — {-1,-2,-3}
Explanation:
Kadane's algorithm doesn't work for all negative numbers. So, the answer is {-1,-2,-3}.
For which of the following inputs would Kadane's algorithm produce the INCORRECT output?
{0,1,2,3}
{-1,0,1}
{-1,-2,-3,0}
{-4,-3,-2,-1}
Correct Answer: D — {-4,-3,-2,-1}
Explanation:
Kadane's algorithm works if the input array contains at least one non-negative element. Every element in the array {-4,-3,-2,-1} is negative. Hence Kadane's algorithm won't work.
Kadane's algorithm uses which of the following techniques?
Divide and conquer
Dynamic programming
Recursion
Greedy algorithm
Correct Answer: B — Dynamic programming
Explanation:
Kadane's algorithm uses dynamic programming.
Kadane's algorithm is used to find ____________
Longest increasing subsequence
Longest palindrome subsequence
Maximum sub-array sum
Longest decreasing subsequence
Correct Answer: C — Maximum sub-array sum
Explanation:
Kadane's algorithm is used to find the maximum sub-array sum for a given array.
Which technique is used by line 7 of the above code?
Greedy
Recursion
Memoization
Overlapping subproblems
Correct Answer: C — Memoization
Explanation:
Line 7 stores the current value that is calculated, so that the value can be used later directly without calculating it from scratch. This is memoization.
Which property is shown by line 7 of the above code?
Optimal substructure
Overlapping subproblems
Both overlapping subproblems and optimal substructure
Greedy substructure
Correct Answer: A — Optimal substructure
Explanation:
We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving subproblems. Hence, line 7 shows the optimal substructure property.
What is the space complexity of the recursive implementation used to find the nth fibonacci term?
O(1)
O(n)
O(n^{2})
O(n^{3})
Correct Answer: A — O(1)
Explanation:
The recursive implementation doesn't store any values and calculates every value from scratch. So, the space complexity is O(1).
