98
81.5k

410+ Design and Analysis of Algorithms Solved MCQs

These multiple-choice questions (MCQs) are designed to enhance your knowledge and understanding in the following areas: Computer Science Engineering (CSE) .

201.

Which of the following methods can be used to solve the matrix chain multiplication problem?

A. dynamic programming
B. brute force
C. recursion
D. dynamic programming, brute force, recursion
Answer» D. dynamic programming, brute force, recursion
Explanation: dynamic programming, brute force, recursion methods can be used to solve the matrix chain multiplication problem.
202.

Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices?

A. 18000
B. 12000
C. 24000
D. 32000
Answer» A. 18000
Explanation: the minimum number of multiplications are 18000. this is the case when the matrices are parenthesized as (p*q)*r.
203.

Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation?

A. o(n!)
B. o(n3)
C. o(n2)
D. exponential
Answer» D. exponential
Explanation: the time complexity of finding all the possible ways of multiplying a set of n matrices is given by (n-1)th catalan number which is exponential.
204.

Which of the following methods can be used to solve the longest common subsequence problem?

A. recursion
B. dynamic programming
C. both recursion and dynamic programming
D. greedy algorithm
Answer» C. both recursion and dynamic programming
Explanation: both recursion and dynamic programming can be used to solve the longest subsequence problem.
205.

Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

A. 9
B. 8
C. 7
D. 6
Answer» C. 7
Explanation: the longest common subsequence is “prtpqrs” and its length is 7.
206.

Which of the following problems can be solved using the longest subsequence problem?

A. longest increasing subsequence
B. longest palindromic subsequence
C. longest bitonic subsequence
D. longest decreasing subsequence
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.
207.

Longest common subsequence is an example of                          

A. greedy algorithm
B. 2d dynamic programming
C. 1d dynamic programming
D. divide and conquer
Answer» B. 2d dynamic programming
Explanation: longest common subsequence is an example of 2d dynamic programming.
208.

What is the time complexity of the brute force algorithm used to find the longest common subsequence?

A. o(n)
B. o(n2)
C. o(n3)
D. o(2n)
Answer» D. o(2n)
Explanation: the time complexity of the brute force algorithm used to find the longest common subsequence is o(2n).
209.

Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ?

A. hgmq
B. cfnq
C. bfmq
D. fgmna
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.
210.

Which of the following methods can be used to solve the longest palindromic subsequence problem?

A. dynamic programming
B. recursion
C. brute force
D. dynamic programming, recursion, brute force
Answer» D. dynamic programming, recursion, brute force
Explanation: dynamic programming, recursion, brute force can be used to solve the longest palindromic subsequence problem.
211.

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

A. abcba
B. abba
C. abbbba
D. adba
Answer» D. adba
Explanation: ‘adba’ is not a palindromic sequence.
212.

For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence?

A. a string that is a palindrome
B. a string of length one
C. a string that has all the same letters(e.g. aaaaaa)
D. some strings of length two
Answer» D. some strings of length two
Explanation: a string of length 2 for eg: ab is not a palindrome.
213.

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

A. 6
B. 7
C. 8
D. 9
Answer» B. 7
Explanation: the longest palindromic subsequence is “abbabba” and its length is 7.
214.

What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?

A. o(1)
B. o(2n)
C. o(n)
D. o(n2)
Answer» B. o(2n)
Explanation: in the brute force algorithm, all the subsequences are found and the length of the longest palindromic subsequence is calculated. this takes exponential time.
215.

For every non-empty string, the length of the longest palindromic subsequence is at least one.

A. true
B. false
Answer» A. true
Explanation: a single character of any string can always be considered as a palindrome and its length is one.
216.

Longest palindromic subsequence is an example of                              

A. greedy algorithm
B. 2d dynamic programming
C. 1d dynamic programming
D. divide and conquer
Answer» B. 2d dynamic programming
Explanation: longest palindromic subsequence is an example of 2d dynamic programming.
217.

Which of the following methods can be used to solve the edit distance problem?

A. recursion
B. dynamic programming
C. both dynamic programming and recursion
D. greedy algorithm
Answer» C. both dynamic programming and recursion
Explanation: both dynamic programming and recursion can be used to solve the edit distance problem.
218.

The edit distance satisfies the axioms of a metric when the costs are non-negative.

A. true
B. false
Answer» A. true
Explanation: d(s,s) = 0, since each string can be transformed into itself without any change. d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.
219.

Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.

A. true
B. false
Answer» A. true
Explanation: consider the strings “abcd” and “efghi”. the string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. the cost of transformation is 5, which is equal to the length of the larger string.
220.

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

A. 3
B. 4
C. 5
D. 6
Answer» B. 4
Explanation: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. so, the edit distance is 4.
221.

Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?

A. 0
B. 4
C. 2
D. 3
Answer» B. 4
Explanation: the empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. thus, the edit distance is 4.
222.

Which of the following is NOT a Catalan number?

A. 1
B. 5
C. 14
D. 43
Answer» D. 43
Explanation: catalan numbers are given by: (2n!)/((n+1)!n!).
223.

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

A. recursion
B. binomial coefficients
C. dynamic programming
D. recursion, binomial coefficients, dynamic programming
Answer» D. recursion, binomial coefficients, dynamic programming
Explanation: all of the mentioned methods can be used to find the nth catalan number.
224.

Which of the following implementations of Catalan numbers has the smallest time complexity?

A. dynamic programming
B. binomial coefficients
C. recursion
D. all have equal time complexity
Answer» B. binomial coefficients
Explanation: The time complexities are as follows:
Dynamic programming: O(n2) Recursion: Exponential Binomial coefficients: O(n).
225.

Which of the following methods can be used to solve the assembly line scheduling problem?

A. recursion
B. brute force
C. dynamic programming
D. all of the mentioned
Answer» D. all of the mentioned
Explanation: all of the above mentioned methods can be used to solve the assembly line scheduling problem.
226.

What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?

A. o(1)
B. o(n)
C. o(n2)
D. o(2n)
Answer» D. o(2n)
Explanation: in the brute force algorithm, all the possible ways are calculated which are of the order of 2n.
227.

In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?

A. 0
B. 1
C. 2
D. 3
Answer» C. 2
Explanation: in the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number.
228.

What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?

A. o(1)
B. o(n)
C. o(n2)
D. o(n3)
Answer» B. o(n)
Explanation: the time complexity of the above dynamic programming implementation of the assembly line scheduling problem is o(n).
229.

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» D. both recursion and dynamic programming
Explanation: dynamic programming and recursion can be used to solve the problem.
230.

In which of the following cases the minimum no of insertions to form palindrome is maximum?

A. string of length one
B. string with all same characters
C. palindromic string
D. non palindromic string
Answer» D. non palindromic string
Explanation: in string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. to convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.
231.

Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?

A. 0
B. 1
C. 2
D. 3
Answer» A. 0
Explanation: the given string is already a palindrome. so, no insertions are required.
232.

Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?

A. minimum number of jumps problem
B. longest common subsequence problem
C. coin change problem
D. knapsack problems
Answer» B. longest common subsequence problem
Explanation: a variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.
233.

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. brute force, recursion, dynamic programming
Answer» D. brute force, recursion, dynamic programming
Explanation: brute force, recursion and dynamic programming can be used to find the submatrix that has the maximum sum.
234.

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. when diagonal elements are positive and rest are negative
Answer» A. when all the elements are negative
Explanation: when all the elements of a matrix are positive, the maximum sum rectangle is the 2d matrix itself.
235.

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» C. 12
Explanation: since all the elements of the 2×3 matrix are positive, the maximum sum rectangle is the matrix itself and the sum of elements is 12.
236.

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» B. -1
Explanation: since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. the sum of elements of the maximum sum rectangle is -1.
237.

The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?

A. hirschberg’s algorithm
B. needleman-wunsch algorithm
C. kadane’s algorithm
D. wagner fischer algorithm
Answer» C. kadane’s algorithm
Explanation: the dynamic programming implementation of the maximum sum rectangle problem uses kadane’s algorithm.
238.

Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem?

A. dynamic programming
B. recursion
C. brute force
D. dynamic programming, recursion, brute force
Answer» D. dynamic programming, recursion, brute force
Explanation: all of the mentioned methods can be used to solve the balanced partition
239.

In which of the following cases, it is not possible to have two subsets with equal sum?

A. when the number of elements is odd
B. when the number of elements is even
C. when the sum of elements is odd
D. when the sum of elements is even
Answer» C. when the sum of elements is odd
Explanation: when the sum of all the elements is odd, it is not possible to have two subsets with equal sum.
240.

What is the time complexity of the brute force algorithm used to solve the balanced partition problem?

A. o(1)
B. o(n)
C. o(n2)
D. o(2n)
Answer» D. o(2n)
Explanation: in the brute force implementation, all the possible subsets will be formed. this takes exponential time.
241.

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. 64
Answer» A. 16
Explanation: the sum of all the elements of the array is 32. so, the sum of all the elements of each partition should be 16.
242.

You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?

A. brute force
B. recursion
C. dynamic programming
D. brute force, recursion and dynamic programming
Answer» D. brute force, recursion and dynamic programming
Explanation: brute force, recursion and dynamic programming can be used to solve the dice throw problem.
243.

You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?

A. n*n*n…f times
B. f*f*f…n times
C. n*n*n…n times
D. f*f*f…f times
Answer» B. f*f*f…n times
Explanation: each die can take f values and there are n dice. so, the total number of permutations is f*f*f…n times.
244.

You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together?

A. 27
B. 36
C. 216
D. 81
Answer» C. 216
Explanation: the total number of permutations that can be obtained is 6 * 6 * 6
245.

You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved?

A. 0
B. 1
C. 2
D. 3
Answer» C. 2
Explanation: the sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.
246.

There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together?

A. 1
B. f
C. n
D. n*f
Answer» C. n
Explanation: the sum will be minimum when all the faces show a value 1. the sum in this case will be n.
247.

There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together?

A. 1
B. f*f
C. n*n
D. n*f
Answer» D. n*f
Explanation: the sum will be maximum when all the faces show a value f. the sum in this case will be n*f.
248.

There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved?

A. 0
B. 2
C. 4
D. 8
Answer» A. 0
Explanation: since there are 10 dice and the minimum value each die can take is 1, the minimum possible sum is 10. hence, a sum of 4 cannot be achieved.
249.

Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

A. 0
B. 1
C. 2
D. 3
Answer» C. 2
Explanation: the expression can be parenthesized as (t & f) ∧ t or t & (f ∧ t), so that the output is t.
250.

Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?

A. n factorial
B. n square
C. n cube
D. nth catalan number
Answer» D. nth catalan number
Explanation: the nth catalan number gives

Done Studing? Take A Test.

Great job completing your study session! Now it's time to put your knowledge to the test. Challenge yourself, see how much you've learned, and identify areas for improvement. Don’t worry, this is all part of the journey to mastery. Ready for the next step? Take a quiz to solidify what you've just studied.