Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?

dp[i,j] = 1 if i=j dp[i,j] = min{dp[i,k] + dp[k+1,j]}

dp[i,j] = 0 if i=j dp[i,j] = min{dp[i,k] + dp[k+1,j]}

dp[i,j] = 1 if i=j dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

dp[i,j] = 0 if i=j dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

When a top-down approach of dynamic programming is applied to a problem, it usually _____________

Increases the time complexity and decreases the space complexity

Decreases both, the time complexity and the space complexity

Decreases the time complexity and increases the space complexity

Increases the time complexity and decreases the space complexity

Increases both, the time complexity and the space complexity

In which of the following cases, the maximum sum rectangle is the 2D matrix itself?

When all the elements are positive

When all the elements are negative

When all the elements are positive

When some elements are positive and some negative

Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?

Both recursion and dynamic programming

In which of the following cases, the maximum sum rectangle can be a 1 x 1 matrix containing the largest element?

When the matrix is a 1×1 matrix

When all the elements of a matrix are zero

When all the elements of the matrix are negative

111 + Mcqs in Dynamic Programming in Data Structures and Algorithms Page 2 McqOptions

51.	What is the time complexity of the above dynamic programming implementation of the matrix chain problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	O(n3)
Answer» E.

Discussion

52.	What is the space complexity of the above implementation of Wagner-Fischer algorithm where “m” and “n” are the lengths of the two strings?
A.	O(1)
B.	O(n+m)
C.	O(mn)
D.	O(nlogm)
Answer» D. O(nlogm)

Discussion

53.	Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?
A.	dp[i,j] = 1 if i=j dp[i,j] = min{dp[i,k] + dp[k+1,j]}
B.	dp[i,j] = 0 if i=j dp[i,j] = min{dp[i,k] + dp[k+1,j]}
C.	dp[i,j] = 1 if i=j dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]mat[k]mat[j].
D.	dp[i,j] = 0 if i=j dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]mat[k]mat[j].
Answer» E.

Discussion

54.	Which of the following methods can be used to find the nth Catalan number?
A.	Recursion
B.	Binomial coefficients
C.	Dynamic programming
D.	All of the mentioned
Answer» E.

Discussion

55.	When a top-down approach of dynamic programming is applied to a problem, it usually _____________
A.	Decreases both, the time complexity and the space complexity
B.	Decreases the time complexity and increases the space complexity
C.	Increases the time complexity and decreases the space complexity
D.	Increases both, the time complexity and the space complexity
Answer» C. Increases the time complexity and decreases the space complexity

Discussion

56.	What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
A.	O(n)
B.	O(logn)
C.	O(nlogn)
D.	O(n2)
Answer» D. O(n2)

Discussion

57.	The following sequence is a fibonacci sequence:0, 1, 1, 2, 3, 5, 8, 13, 21,…..Which technique can be used to get the nth fibonacci term?
A.	Recursion
B.	Dynamic programming
C.	A single for loop
D.	All of the mentioned
Answer» E.

Discussion

58.	You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
A.	O(N)
B.	O(S)
C.	O(N2)
D.	O(S*N)
Answer» E.

Discussion

59.	You are given infinite coins of denominations 5, 7, 9. Which of the following sum CANNOT be achieved using these coins?
A.	50
B.	21
C.	13
D.	23
Answer» D. 23

Discussion

60.	Find the maximum sub-array sum for the given elements. {2, -1, 3, -4, 1, -2, -1, 5, -4}
A.	3
B.	5
C.	8
D.	6
Answer» C. 8

Discussion

61.	You are given infinite coins of denominations 3, 5, 7. Which of the following sum CAN be achieved using these coins?
A.	15
B.	16
C.	17
D.	All of the mentioned
Answer» E.

Discussion

62.	Find the maximum sub-array sum for the given elements. {-2, -1, -3, -4, -1, -2, -1, -5, -4}
A.	-3
B.	5
C.	3
D.	-1
Answer» E.

Discussion

63.	Find the maximum sub-array sum for the following array: {3, 6, 7, 9, 3, 8}
A.	33
B.	36
C.	23
D.	26
Answer» C. 23

Discussion

64.	Suppose you are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?
A.	O(N)
B.	O(S)
C.	O(N2)
D.	O(S*N)
Answer» C. O(N2)

Discussion

65.	What is the space complexity of the above dynamic programming implementation of the boolean parenthesization problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	O(n3)
Answer» D. O(n3)

Discussion

66.	Kadane's algorithm is used to find ____________
A.	Longest increasing subsequence
B.	Longest palindrome subsequence
C.	Maximum sub-array sum
D.	All of the mentioned
Answer» D. All of the mentioned

Discussion

67.	You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________
A.	Greedy algorithm
B.	Dynamic programming
C.	Divide and conquer
D.	All of the mentioned
Answer» C. Divide and conquer

Discussion

68.	For which of the following inputs would Kadane's algorithm produce the CORRECT output?
A.	{0,1,2,3}
B.	{-1,0,1}
C.	{-1,-2,-3,0}
D.	All of the mentioned
Answer» E.

Discussion

69.	What is the time complexity of the above dynamic programming implementation of the balanced partition problem where “n” is the number of elements and “sum” is their sum?
A.	O(sum)
B.	O(n)
C.	O(sum * n)
D.	O(sum + n)
Answer» D. O(sum + n)

Discussion

70.	What is the space complexity of the above dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings?
A.	O(1)
B.	O(m + n)
C.	O(mn)
D.	None of the mentioned
Answer» D. None of the mentioned

Discussion

71.	What is the time complexity of the above dynamic programming implementation of the boolean parenthesization problem?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	O(n3)
Answer» E.

Discussion

72.	What is the length of the longest palindromic subsequence for the string “ababcdabba”?
A.	6
B.	7
C.	8
D.	9
Answer» C. 8

Discussion

73.	Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
A.	3
B.	4
C.	5
D.	6
Answer» C. 5

Discussion

74.	You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?
A.	1
B.	2
C.	3
D.	4
Answer» C. 3

Discussion

75.	What is the time complexity of the above dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?
A.	O(n)
B.	O(1)
C.	O(n2)
D.	None of the mentioned
Answer» D. None of the mentioned

Discussion

76.	Which of the following strings is a palindromic subsequence of the string “ababcdabba”?
A.	abcba
B.	abba
C.	abbbba
D.	all of the mentioned
Answer» E.

Discussion

77.	Find the longest increasing subsequence for the given sequence: {10, -10, 12, 9, 10, 15, 13, 14}
A.	{10, 12, 15}
B.	{10, 12, 13, 14}
C.	{-10, 12, 13, 14}
D.	{-10, 9, 10, 13, 14}
Answer» E.

Discussion

78.	What is the time complexity of the ABOVE dynamic programming implementation used to compute the nth fibonacci term?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	Exponential
Answer» C. O(n2)

Discussion

79.	Find the length of the longest increasing subsequence for the given sequence: {-10, 24, -9, 35, -21, 55, -41, 76, 84}
A.	5
B.	4
C.	3
D.	6
Answer» E.

Discussion

80.	What is the space complexity of the above dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?
A.	O(n)
B.	O(1)
C.	O(n2)
D.	None of the mentioned
Answer» D. None of the mentioned

Discussion

81.	What is the space complexity of the ABOVE dynamic programming implementation used to find the minimum number of jumps?
A.	O(1)
B.	O(n)
C.	O(n2)
D.	None of the mentioned
Answer» C. O(n2)

Discussion

82.	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 __________
A.	Recursion
B.	Dynamic programming
C.	Brute force
D.	All of the mentioned
Answer» E.

Discussion

83.	Consider the 3×3 matrix {{2,1,-3},{6,3,4},{-2,3,0}}. What is the sum of the elements of the maximum sum rectangle?
A.	13
B.	16
C.	14
D.	19
Answer» D. 19

Discussion

84.	Which of the following problems should be solved using dynamic programming?
A.	Mergesort
B.	Binary search
C.	Longest common subsequence
D.	Quicksort
Answer» D. Quicksort

Discussion

85.	The number of increasing subsequences with the longest length for the given sequence are: {10, 9, 8, 7, 6, 5}
A.	3
B.	4
C.	5
D.	6
Answer» E.

Discussion

86.	Consider the following array: {1, 3, 5, 8, 9, 2, 6, 7, 6}What is the minimum number of jumps required to reach the end of the array?
A.	1
B.	2
C.	3
D.	4
Answer» D. 4

Discussion

87.	For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.
A.	True
B.	False
Answer» C.

Discussion

88.	In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.
A.	True
B.	False
Answer» C.

Discussion

89.	Consider a matrix in which all the elements are non-zero(at least one positive and at least one negative element). In this case, the sum of the elements of the maximum sum rectangle cannot be zero.
A.	True
B.	False
Answer» B. False

Discussion

90.	Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?
A.	Brute force
B.	Recursion
C.	Dynamic programming
D.	All of the mentioned
Answer» E.

Discussion

91.	What is the edit distance between the strings “abcd” and “acbd” when the allowed operations are insertion, deletion and substitution?
A.	1
B.	2
C.	3
D.	4
Answer» C. 3

Discussion

92.	In which of the following cases, the maximum sum rectangle is the 2D matrix itself?
A.	When all the elements are negative
B.	When all the elements are positive
C.	When some elements are positive and some negative
D.	None of the mentioned
Answer» B. When all the elements are positive

Discussion

93.	Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
A.	Greedy algorithm
B.	Recursion
C.	Dynamic programming
D.	Both recursion and dynamic programming
Answer» E.

Discussion

94.	In which of the following cases, the maximum sum rectangle can be a 1 x 1 matrix containing the largest element?
A.	When the matrix is a 1×1 matrix
B.	When all the elements of a matrix are zero
C.	When all the elements of the matrix are negative
D.	All of the mentioned
Answer» E.

Discussion

95.	What is space complexity of the above dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?
A.	O(n*f)
B.	O(f*s)
C.	O(n*s)
D.	O(nfs)
Answer» D. O(nfs)

Discussion

96.	You are given a boolean expression which consists of operators &, \| and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?
A.	Dynamic programming
B.	Recursion
C.	Brute force
D.	All of the mentioned
Answer» E.

Discussion

97.	What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?
A.	16
B.	32
C.	0
D.	None of the mentioned
Answer» B. 32

Discussion

98.	Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?
A.	3
B.	6
C.	12
D.	18
Answer» D. 18

Discussion

99.	Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?
A.	0
B.	-1
C.	-7
D.	-12
Answer» C. -7

Discussion

100.	What is time complexity of the above dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?
A.	O(n*f)
B.	O(f*s)
C.	O(n*s)
D.	O(nfs)
Answer» E.

Discussion

Explore topic-wise MCQs in Data Structures and Algorithms.

What is the time complexity of the above dynamic programming implementation of the matrix chain problem?

What is the space complexity of the above implementation of Wagner-Fischer algorithm where “m” and “n” are the lengths of the two strings?

Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?

Which of the following methods can be used to find the nth Catalan number?

When a top-down approach of dynamic programming is applied to a problem, it usually _____________

What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array sum?

The following sequence is a fibonacci sequence:0, 1, 1, 2, 3, 5, 8, 13, 21,…..Which technique can be used to get the nth fibonacci term?

You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?

You are given infinite coins of denominations 5, 7, 9. Which of the following sum CANNOT be achieved using these coins?

Find the maximum sub-array sum for the given elements. {2, -1, 3, -4, 1, -2, -1, 5, -4}

You are given infinite coins of denominations 3, 5, 7. Which of the following sum CAN be achieved using these coins?

Find the maximum sub-array sum for the given elements. {-2, -1, -3, -4, -1, -2, -1, -5, -4}

Find the maximum sub-array sum for the following array: {3, 6, 7, 9, 3, 8}

Suppose you are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?

What is the space complexity of the above dynamic programming implementation of the boolean parenthesization problem?

Kadane's algorithm is used to find ____________

You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________

For which of the following inputs would Kadane's algorithm produce the CORRECT output?

What is the time complexity of the above dynamic programming implementation of the balanced partition problem where “n” is the number of elements and “sum” is their sum?

What is the space complexity of the above dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings?

What is the time complexity of the above dynamic programming implementation of the boolean parenthesization problem?

What is the length of the longest palindromic subsequence for the string “ababcdabba”?

Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?

You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?

What is the time complexity of the above dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?

Which of the following strings is a palindromic subsequence of the string “ababcdabba”?

Find the longest increasing subsequence for the given sequence: {10, -10, 12, 9, 10, 15, 13, 14}

What is the time complexity of the ABOVE dynamic programming implementation used to compute the nth fibonacci term?

Find the length of the longest increasing subsequence for the given sequence: {-10, 24, -9, 35, -21, 55, -41, 76, 84}

What is the space complexity of the above dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?

What is the space complexity of the ABOVE dynamic programming implementation used to find the minimum number of jumps?

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 __________

Consider the 3×3 matrix {{2,1,-3},{6,3,4},{-2,3,0}}. What is the sum of the elements of the maximum sum rectangle?

Which of the following problems should be solved using dynamic programming?

The number of increasing subsequences with the longest length for the given sequence are: {10, 9, 8, 7, 6, 5}

Consider the following array: {1, 3, 5, 8, 9, 2, 6, 7, 6}What is the minimum number of jumps required to reach the end of the array?

For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.

In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.

Consider a matrix in which all the elements are non-zero(at least one positive and at least one negative element). In this case, the sum of the elements of the maximum sum rectangle cannot be zero.

Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?

What is the edit distance between the strings “abcd” and “acbd” when the allowed operations are insertion, deletion and substitution?

In which of the following cases, the maximum sum rectangle is the 2D matrix itself?

Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?

In which of the following cases, the maximum sum rectangle can be a 1 x 1 matrix containing the largest element?

What is space complexity of the above dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?

What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?

Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?

Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?

What is time complexity of the above dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?