410+ Design and Analysis of Algorithms Solved MCQs

70

55.1k

2

201.	Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?
A.	robert floyd
B.	stephen warshall
C.	bernard roy
D.	peter ingerman
Answer» D. peter ingerman
Explanation: the modern formulation of floyd-warshall algorithm as three nested for- loops was proposed by peter ingerman in the year 1962.

discuss

202.	What happens when the value of k is 0 in the Floyd Warshall Algorithm?
A.	1 intermediate vertex
B.	0 intermediate vertex
C.	n intermediate vertices
D.	n-1 intermediate vertices
Answer» B. 0 intermediate vertex
Explanation: when k=0, a path from vertex i to vertex j has no intermediate vertices at all. such a path has at most one edge and hence dij(0) = wij.

discuss

203.	Using logical operator’s instead arithmetic operators saves time and space.
A.	true
B.	false
Answer» A. true
Explanation: in computers, logical operations on single bit values execute faster than arithmetic operations on integer words of data.

discuss

204.	The time taken to compute the transitive closure of a graph is Theta(n2).
A.	true
B.	false
Answer» B. false
Explanation: the time taken to compute the transitive closure of a graph is theta(n3).

discuss

205.	If a problem can be broken into subproblems which are reused several times, the problem possesses property.
A.	overlapping subproblems
B.	optimal substructure
C.	memoization
D.	greedy
Answer» A. overlapping subproblems
Explanation: overlapping subproblems is the property in which value of a subproblem is used several times.

discuss

206.	When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.
A.	true
B.	false
Answer» A. true
Explanation: dynamic programming calculates the value of a subproblem only once, while other methods that don’t take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. so, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don’t take advantage of the overlapping subproblems property.

discuss

207.	A greedy algorithm can be used to solve all the dynamic programming problems.
A.	true
B.	false
Answer» B. false
Explanation: a greedy algorithm gives optimal solution for all subproblems, but when these locally optimal solutions are combined it may not result into a globally optimal solution. hence, a greedy algorithm cannot be used to solve all the dynamic programming problems.

discuss

208.	In dynamic programming, the technique of storing the previously calculated values is called
A.	saving value property
B.	storing value property
C.	memoization
D.	mapping
Answer» C. memoization
Explanation: memoization is the technique

discuss

209.	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» B. decreases the time complexity and increases the space complexity
Explanation: the top-down approach uses the memoization technique which stores the previously calculated values. due to this, the time complexity is decreased but the space complexity is increased.

discuss

210.	Which of the following problems is NOT solved using dynamic programming?
A.	0/1 knapsack problem
B.	matrix chain multiplication problem
C.	edit distance problem
D.	fractional knapsack problem
Answer» D. fractional knapsack problem
Explanation: the fractional knapsack problem is solved using a greedy algorithm.

discuss

211.	Which of the following problems should be solved using dynamic programming?
A.	mergesort
B.	binary search
C.	longest common subsequence
D.	quicksort
Answer» C. longest common subsequence
Explanation: the longest common subsequence problem has both, optimal substructure and overlapping subproblems. hence, dynamic programming should be used the solve this problem.

discuss

212.	What is the time complexity of the recursive implementation used to find the nth fibonacci term?
A.	o(1)
B.	o(n2)
C.	o(n!)
D.	exponential
Answer» D. exponential
Explanation: the recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). so, the time complexity is given by:

discuss

213.	What is the space complexity of the recursive implementation used to find the nth fibonacci term?
A.	o(1)
B.	o(n)
C.	o(n2)
D.	o(n3)
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).

discuss

214.	return fibo_terms[n]
A.	o(1)
B.	o(n)
C.	o(n2)
D.	exponential
Answer» B. o(n)
Explanation: to calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time.

discuss

215.	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.	backtracking
Answer» B. dynamic programming
Explanation: the coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can

discuss

216.	Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
A.	14
B.	10
C.	6
D.	100
Answer» D. 100
Explanation: using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. but, the optimal answer is two coins {3,3}. similarly, four coins {4,4,1,1} will be selected to make a sum of 10. but, the optimal answer is three coins {4,3,3}. also, five coins {4,4,4,1,1} will be selected to make a sum of 14. but, the optimal answer is four coins {4,4,3,3}. for a sum of 100, twenty-five coins {all 4’s} will be selected and the optimal answer is also twenty-five coins {all 4’s}.

discuss

217.	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» D. o(s*n)
Explanation: the time complexity is o(s*n).

discuss

218.	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» B. 2
Explanation: a sum of 7 can be achieved by using a minimum of two coins {3,4}.

discuss

219.	What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
A.	o(n)
B.	o(1)
C.	o(n!)
D.	o(n2)
Answer» B. o(1)
Explanation: the divide and conquer algorithm uses a constant space. so, the space complexity is o(1).

discuss

220.	Kadane’s algorithm is used to find
A.	longest increasing subsequence
B.	longest palindrome subsequence
C.	maximum sub-array sum
D.	longest decreasing subsequence
Answer» C. maximum sub-array sum
Explanation: kadane’s algorithm is used to find the maximum sub-array sum for a given array.

discuss

221.	Kadane’s algorithm uses which of the following techniques?
A.	divide and conquer
B.	dynamic programming
C.	recursion
D.	greedy algorithm
Answer» B. dynamic programming
Explanation: kadane’s algorithm uses dynamic programming.

discuss

222.	For which of the following inputs would Kadane’s algorithm produce a WRONG output?
A.	{1,0,-1}
B.	{-1,-2,-3}
C.	{1,2,3}
D.	{0,0,0}
Answer» B. {-1,-2,-3}
Explanation: kadane’s algorithm doesn’t work for all negative numbers. so, the answer is {-1,-2,-3}.

discuss

223.	What is the time complexity of Kadane’s algorithm?
A.	o(1)
B.	o(n)
C.	o(n2)
D.	o(5)
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.

discuss

224.	What is the space complexity of Kadane’s algorithm?
A.	o(1)
B.	o(n)
C.	o(n2)
D.	none of the mentioned
Answer» A. o(1)
Explanation: kadane’s algorithm uses a constant space. so, the space complexity is

discuss

225.	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.	recursion, dynamic programming, brute force
Answer» D. recursion, dynamic programming, brute force
Explanation: the longest increasing subsequence problem can be solved using all of the mentioned methods.

discuss

226.	For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.
A.	true
B.	false
Answer» B. false
Explanation: for a given sequence, it is possible that there is more than one subsequence with the longest length.

discuss

227.	Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?
A.	brute force
B.	dynamic programming
C.	recursion
D.	brute force, dynamic programming and recursion
Answer» D. brute force, dynamic programming and recursion
Explanation: brute force, dynamic programming and recursion can be used to solve the rod cutting problem.

discuss

228.	Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?
A.	o(n2)
B.	o(n3)
C.	o(nlogn)
D.	o(2n)
Answer» D. o(2n)
Explanation: the brute force implementation finds all the possible cuts. this takes o(2n) time.

discuss

229.	For every rod cutting problem there will be a unique set of pieces that give the maximum price.
A.	true
B.	false
Answer» B. false
Explanation: consider a rod of length 3. the prices are {2,3,6} for lengths {1,2,3} respectively. the pieces {1,1,1} and {3} both give the maximum value of 6.

discuss

230.	For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.
A.	true
B.	false
Answer» A. true
Explanation: consider the array {1,2,3,4,5}. it is possible to reach the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}.

discuss

231.	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» B. false
Explanation: consider the array {1,0,2,3,4}.

discuss

232.	What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps?
A.	o(1)
B.	o(n)
C.	o(n2)
D.	o(5)
Answer» B. o(n)
Explanation: the space complexity of the above dynamic programming implementation is o(n).

discuss

233.	The Knapsack problem 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: knapsack problem is an example of 2d dynamic programming.

discuss

234.	Which of the following problems is equivalent to the 0-1 Knapsack problem?
A.	you are given a bag that can carry a maximum weight of w. you are given n items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. you can break the items into smaller pieces. choose the items in such a way that you get the maximum value
B.	you are studying for an exam and you have to study n questions. the questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. you can study for a maximum of t hours. you can either study a question or leave it. choose the questions in such a way that your score is maximized
C.	you are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum s. you have to find the minimum number of coins required to get the sum s
D.	you are given a suitcase that can carry a maximum weight of 15kg. you are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. you can break the items into smaller pieces. choose the items in such a way that you get the maximum value
Answer» B. you are studying for an exam and you have to study n questions. the questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. you can study for a maximum of t hours. you can either study a question or leave it. choose the questions in such a way that your score is maximized
Explanation: in this case, questions are used instead of items. each question has a score which is same as each item having a value.

discuss

235.	The 0-1 Knapsack problem can be solved using Greedy algorithm.
A.	true
B.	false
Answer» B. false
Explanation: the knapsack problem cannot be solved using the greedy algorithm.

discuss

236.	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.

discuss

237.	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 (pq)r.

discuss

238.	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.

discuss

239.	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.

discuss

240.	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.

discuss

241.	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.

discuss

242.	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.

discuss

243.	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).

discuss

244.	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.

discuss

245.	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.

discuss

246.	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.

discuss

247.	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.

discuss

248.	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.

discuss

249.	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.

discuss

250.	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.

discuss

251.	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.

discuss

252.	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.

discuss

253.	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.

discuss

254.	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.

discuss

255.	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.

discuss

256.	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.

discuss

257.	What is the time complexity of the 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» C. o(mn)
Explanation: the time complexity of the wagner–fischer algorithm is o(mn).

discuss

258.	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!).

discuss

259.	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.

discuss

260.	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).

discuss

261.	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.

discuss

262.	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.

discuss

263.	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.

discuss

264.	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).

discuss

265.	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.

discuss

266.	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.

discuss

267.	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
C.	answer: b
D.	explanation: in the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. for example, consider the string “abc”. the string can be converted to “abcba” by inserting “a” and “b”. the number of insertions is two, which is equal to length minus one.
Answer» B. false
Explanation: the string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. thus, only one insertion is required.

discuss

268.	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.

discuss

269.	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.

discuss

270.	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.

discuss

271.	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.

discuss

272.	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.

discuss

273.	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.

discuss

274.	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.

discuss

275.	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

discuss

276.	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.

discuss

277.	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.

discuss

278.	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.

discuss

279.	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.

discuss

280.	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.	nnn…f times
B.	fff…n times
C.	nnn…n times
D.	fff…f times
Answer» B. fff…n times
Explanation: each die can take f values and there are n dice. so, the total number of permutations is fff…n times.

discuss

281.	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

discuss

282.	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}.

discuss

283.	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.

discuss

284.	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.

discuss

285.	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.

discuss

286.	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.

discuss

287.	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

discuss

288.	What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?
A.	nth catalan number
B.	n factorial
C.	n cube
D.	n square
Answer» A. nth catalan number
Explanation: the number of ways will be maximum when all the possible

discuss

289.	Which of the following is true?
A.	prim’s algorithm can also be used for disconnected graphs
B.	kruskal’s algorithm can also run on the disconnected graphs
C.	prim’s algorithm is simpler than kruskal’s algorithm
D.	in kruskal’s sort edges are added to mst in decreasing order of their weights
Answer» B. kruskal’s algorithm can also run on the disconnected graphs
Explanation: prim’s algorithm iterates from one node to another, so it can not be applied for disconnected graph. kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest. kruskal’s algorithm is comparatively easier and simpler than prim’s algorithm.

discuss

290.	Consider the graph shown below. Which of the following are the edges in the MST of the given graph?
A.	(a-c)(c-d)(d-b)(d-b)
B.	(c-a)(a-d)(d-b)(d-e)
C.	(a-d)(d-c)(d-b)(d-e)
D.	(c-a)(a-d)(d-c)(d-b)(d-e)
Answer» C. (a-d)(d-c)(d-b)(d-e)
Explanation: the minimum spanning tree of the given graph is shown below. it has cost 56.

discuss

291.	Fractional knapsack problem is also known as
A.	0/1 knapsack problem
B.	continuous knapsack problem
C.	divisible knapsack problem
D.	non continuous knapsack problem
Answer» B. continuous knapsack problem
Explanation: fractional knapsack problem is also called continuous knapsack problem.

discuss

292.	Fractional knapsack problem is solved most efficiently by which of the following algorithm?
A.	divide and conquer
B.	dynamic programming
C.	greedy algorithm
D.	backtracking
Answer» C. greedy algorithm
Explanation: greedy algorithm is used to solve this problem. we first sort items according to their value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. at the end, we add the next item as much as we can.

discuss

293.	What is the objective of the knapsack problem?
A.	to get maximum total value in the knapsack
B.	to get minimum total value in the knapsack
C.	to get maximum weight in the knapsack
D.	to get minimum weight in the knapsack
Answer» A. to get maximum total value in the knapsack
Explanation: the objective is to fill the knapsack of some given volume with different materials such that the value of selected items is maximized.

discuss

294.	Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct?
A.	in 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible
B.	both are the same
C.	0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming
D.	in 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible
Answer» D. in 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible
Explanation: in fractional knapsack problem we can partially include an item into the knapsack whereas in 0/1 knapsack we have to either include or exclude the item wholly.

discuss

295.	Time complexity of fractional knapsack problem is
A.	o(n log n)
B.	o(n)
C.	o(n2)
D.	o(nw)
Answer» A. o(n log n)
Explanation: as the main time taking a step is of sorting so it defines the time complexity of our code. so the time complexity will be o(n log n) if we use quick sort for sorting.

discuss

296.	Fractional knapsack problem can be solved in time O(n).
A.	true
B.	false
Answer» A. true
Explanation: it is possible to solve the problem in o(n) time by adapting the algorithm for finding weighted medians.

discuss

297.	Find the maximum value output assuming items to be divisible.
A.	60
B.	80
C.	100
D.	40
Answer» A. 60
Explanation: the value/weight ratio are-

discuss

298.	The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
A.	true
B.	false
Answer» A. true
Explanation: as fractional knapsack gives extra liberty to include the object partially which is not possible with 0/1 knapsack, thus

discuss

299.	The main time taking step in fractional knapsack problem is
A.	breaking items into fraction
B.	adding items into knapsack
C.	sorting
D.	looping through sorted items
Answer» C. sorting
Explanation: the main time taking step is to sort the items according to their value/weight ratio. it defines the time complexity of the code.

discuss

300.	Find the maximum value output assuming items to be divisible and nondivisible respectively.
A.	100, 80
B.	110, 70
C.	130, 110
D.	110, 80
Answer» D. 110, 80
Explanation: assuming items to be divisible- the value/weight ratio are {3, 2, 4}.so we include third and first items wholly. so, now only 15 units of volume are left for second item. so we include it partially.

discuss

410+ Design and Analysis of Algorithms Solved MCQs

Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?

What happens when the value of k is 0 in the Floyd Warshall Algorithm?

Using logical operator’s instead arithmetic operators saves time and space.

The time taken to compute the transitive closure of a graph is Theta(n2).

If a problem can be broken into subproblems which are reused several times, the problem possesses property.

When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.

A greedy algorithm can be used to solve all the dynamic programming problems.

In dynamic programming, the technique of storing the previously calculated values is called

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

Which of the following problems is NOT solved using dynamic programming?

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

What is the time complexity of the recursive implementation used to find the nth fibonacci term?

What is the space complexity of the recursive implementation used to find the nth fibonacci term?

return fibo_terms[n]

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

Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?

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 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?

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

Kadane’s algorithm is used to find

Kadane’s algorithm uses which of the following techniques?

For which of the following inputs would Kadane’s algorithm produce a WRONG output?

What is the time complexity of Kadane’s algorithm?

What is the space complexity of Kadane’s algorithm?

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

For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.

Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?

Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?

For every rod cutting problem there will be a unique set of pieces that give the maximum price.

For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.

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.

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

The Knapsack problem is an example of

Which of the following problems is equivalent to the 0-1 Knapsack problem?

The 0-1 Knapsack problem can be solved using Greedy algorithm.

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

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?

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?

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

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

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

Longest common subsequence is an example of

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

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

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

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

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

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

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

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

Longest palindromic subsequence is an example of

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

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

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.

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

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

What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?

Which of the following is NOT a Catalan number?

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

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

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

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

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

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

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 minimum no of insertions to form palindrome is maximum?

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 the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?

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

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

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

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?

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

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?

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

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

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

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?