Design and Analysis of Algorithms

3 of 5 sets

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

Explanation:- the modern formulation of floyd-warshall algorithm as three nested for- loops was
proposed by peter ingerman in the year 1962.

202. What happens when the value of k is 0 in the o

m
. c Floyd Warshall Algorithm?
A. 1 intermediate vertex
t e
B. 0 intermediate vertex
a
C. n intermediate vertices
q M
c
D. n-1 intermediate vertices
Answer:B
M
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.

203. Using logical operator’s instead arithmetic operators saves time and space.
A. true
B. false
Answer:A

Explanation:- in computers, logical operations on single bit values execute faster than arithmetic
operations on integer words of data.

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

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

Explanation:- overlapping subproblems is the property in which value of a subproblem is used

several times.

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

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.

207. A greedy algorithm can be used to solve all the dynamic programming
problems.
A. true
B. false
Answer:B

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.

208. In dynamic programming, the technique of storing the previously calculated

values is called
A. saving value property
B. storing value property

View all MCQ's at McqMate.com

 C. memoization
D. mapping
Answer:C

Explanation:- memoization is the technique

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

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.

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

Explanation:- the fractional knapsack problem is solved using a greedy algorithm.

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

Explanation:- the longest common subsequence problem has both, optimal substructure and
overlapping subproblems. hence, dynamic programming should be used the solve this problem.

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

View all MCQ's at McqMate.com

 A. o(1)
B. o(n2)
C. o(n!)
D. exponential
Answer:D

Explanation:- the recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). so, the time
complexity is given by:

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

Explanation:- the recursive implementation doesn’t store any values and calculates every value from
scratch. so, the space complexity is o(1).

214. return fibo_terms[n]

A. o(1)
B. o(n)
C. o(n2)
D. exponential
Answer:B

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.

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

View all MCQ's at McqMate.com

Explanation:- the coin change problem has overlapping subproblems(same subproblems are solved
multiple times) and optimal substructure(the solution to the problem can

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

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

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

Explanation:- the time complexity is o(s*n).

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

Explanation:- a sum of 7 can be achieved by using a minimum of two coins {3,4}.

View all MCQ's at McqMate.com

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

Explanation:- the divide and conquer algorithm uses a constant space. so, the space complexity is
o(1).

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

Explanation:- kadane’s algorithm is used to find the maximum sub-array sum for a given array.

221. Kadane’s algorithm uses which of the following techniques?

A. divide and conquer
B. dynamic programming
C. recursion
D. greedy algorithm
Answer:B

Explanation:- kadane’s algorithm uses dynamic programming.

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

Explanation:- kadane’s algorithm doesn’t work for all negative numbers. so, the answer is {-1,-2,-3}.

223. What is the time complexity of Kadane’s algorithm?

View all MCQ's at McqMate.com

 A. o(1)
B. o(n)
C. o(n2)
D. o(5)
Answer:B

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.

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

Explanation:- kadane’s algorithm uses a constant space. so, the space complexity is

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

Explanation:- the longest increasing subsequence problem can be solved using all of the mentioned
methods.

226. For any given sequence, there will ALWAYS be a unique increasing
subsequence with the longest length.
A. true
B. false
Answer:B

Explanation:- for a given sequence, it is possible that there is more than one subsequence with the
longest length.

View all MCQ's at McqMate.com

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

Explanation:- brute force, dynamic programming and recursion can be used to solve the rod cutting
problem.

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

Explanation:- the brute force implementation finds all the possible cuts. this takes o(2n) time.

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

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.

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

View all MCQ's at McqMate.com

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

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

Explanation:- consider the array {1,0,2,3,4}.

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

Explanation:- the space complexity of the above dynamic programming implementation is o(n).

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

Explanation:- knapsack problem is an example of 2d dynamic programming.

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

View all MCQ's at McqMate.com

 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

Explanation:- in this case, questions are used instead of items. each question has a score which is
same as each item having a value.

235. The 0-1 Knapsack problem can be solved using Greedy algorithm.
A. true
B. false
Answer:B

Explanation:- the knapsack problem cannot be solved using the greedy algorithm.

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

Explanation:- dynamic programming, brute force, recursion methods can be used to solve the matrix
chain multiplication problem.

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

Explanation:- the minimum number of multiplications are 18000. this is the case when the matrices
are parenthesized as (p*q)*r.

View all MCQ's at McqMate.com

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

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.

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

Explanation:- both recursion and dynamic programming can be used to solve the longest
subsequence problem.

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

Explanation:- the longest common subsequence is “prtpqrs” and its length is 7.

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

View all MCQ's at McqMate.com

Answer:B

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.

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

Explanation:- longest common subsequence is an example of 2d dynamic programming.

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

Explanation:- the time complexity of the brute force algorithm used to find the longest common
subsequence is o(2n).

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

Explanation:- the length of the longest common subsequence is 4. but ‘fgmna’ is not the longest
common subsequence as its length is 5.

245. Which of the following methods can be used to solve the longest palindromic
subsequence problem?
A. dynamic programming
B. recursion

View all MCQ's at McqMate.com

 C. brute force
D. dynamic programming, recursion, brute force
Answer:D

Explanation:- dynamic programming, recursion, brute force can be used to solve the longest
palindromic subsequence problem.

246. Which of the following is not a palindromic subsequence of the string

“ababcdabba”?
A. abcba
B. abba
C. abbbba
D. adba
Answer:D

Explanation:- ‘adba’ is not a palindromic sequence.

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

Explanation:- a string of length 2 for eg: ab is not a palindrome.

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

Explanation:- the longest palindromic subsequence is “abbabba” and its length is 7.

249. What is the time complexity of the brute force algorithm used to find the
length of the longest palindromic subsequence?
A. o(1)

View all MCQ's at McqMate.com

 B. o(2n)
C. o(n)
D. o(n2)
Answer:B

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.

250. For every non-empty string, the length of the longest palindromic subsequence
is at least one.
A. true
B. false
Answer:A

Explanation:- a single character of any string can always be considered as a palindrome and its
length is one.

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

Explanation:- longest palindromic subsequence is an example of 2d dynamic programming.

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

Explanation:- both dynamic programming and recursion can be used to solve the edit distance
problem.

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

View all MCQ's at McqMate.com

 B. false
Answer:A

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.

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

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.

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

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.

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

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.

View all MCQ's at McqMate.com

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

Explanation:- the time complexity of the wagner–fischer algorithm is o(mn).

258. Which of the following is NOT a Catalan number?

A. 1
B. 5
C. 14
D. 43
Answer:D

Explanation:- catalan numbers are given by: (2n!)/((n+1)!n!).

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

Explanation:- all of the mentioned methods can be used to find the nth catalan number.

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

Explanation:- The time complexities are as follows:

Dynamic programming: O(n2) Recursion: Exponential Binomial coefficients: O(n).

View all MCQ's at McqMate.com

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

Explanation:- all of the above mentioned methods can be used to solve the assembly line
scheduling problem.

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

Explanation:- in the brute force algorithm, all the possible ways are calculated which are of the order
of 2n.

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

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.

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)

View all MCQ's at McqMate.com

 D. o(n3)
Answer:B

Explanation:- the time complexity of the above dynamic programming implementation of the
assembly line scheduling problem is o(n).

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

Explanation:- dynamic programming and recursion can be used to solve the problem.

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

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.

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

View all MCQ's at McqMate.com

 two, which is equal to length minus one.
Answer:B

Explanation:- the string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”.
thus, only one insertion is required.

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

Explanation:- the given string is already a palindrome. so, no insertions are required.

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

Explanation:- a variation of longest common subsequence can be used to solve the minimum
number of insertions to form a palindrome problem.

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

Explanation:- brute force, recursion and dynamic programming can be used to find the submatrix
that has the maximum sum.

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

View all MCQ's at McqMate.com

 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

Explanation:- when all the elements of a matrix are positive, the maximum sum rectangle is the 2d
matrix itself.

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

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.

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

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.

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

View all MCQ's at McqMate.com

Explanation:- the dynamic programming implementation of the maximum sum rectangle problem
uses kadane’s algorithm.

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

Explanation:- all of the mentioned methods can be used to solve the balanced partition

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

Explanation:- when the sum of all the elements is odd, it is not possible to have two subsets with
equal sum.

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

Explanation:- in the brute force implementation, all the possible subsets will be formed. this takes
exponential time.

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

View all MCQ's at McqMate.com

 B. 32
C. 0
D. 64
Answer:A

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.

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

Explanation:- brute force, recursion and dynamic programming can be used to solve the dice throw
problem.

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

Explanation:- each die can take f values and there are n dice. so, the total number of permutations
is f*f*f…n times.

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

Explanation:- the total number of permutations that can be obtained is 6 * 6 * 6

View all MCQ's at McqMate.com

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

Explanation:- the sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.

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

Explanation:- the sum will be minimum when all the faces show a value 1. the sum in this case will
be n.

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

Explanation:- the sum will be maximum when all the faces show a value f. the sum in this case will
be n*f.

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

View all MCQ's at McqMate.com

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.

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

Explanation:- the expression can be parenthesized as (t & f) ? t or t & (f ? t), so that the output is t.

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

Explanation:- the nth catalan number gives

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

Explanation:- the number of ways will be maximum when all the possible

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

View all MCQ's at McqMate.com

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.

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

Explanation:- the minimum spanning tree of the given graph is shown below. it has cost 56.

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

Explanation:- fractional knapsack problem is also called continuous knapsack problem.

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

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.

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

View all MCQ's at McqMate.com

 D. to get minimum weight in the knapsack
Answer:A

Explanation:- the objective is to fill the knapsack of some given volume with different materials such
that the value of selected items is maximized.

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

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.

295. Time complexity of fractional knapsack problem is

A. o(n log n)
B. o(n)
C. o(n2)
D. o(nw)
Answer:A

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.

296. Fractional knapsack problem can be solved in time O(n).

A. true
B. false
Answer:A

Explanation:- it is possible to solve the problem in o(n) time by adapting the algorithm for finding
weighted medians.

297. Find the maximum value output assuming items to be divisible.

A. 60
B. 80

View all MCQ's at McqMate.com

 C. 100
D. 40
Answer:A

Explanation:- the value/weight ratio are-

298. The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
A. true
B. false
Answer:A

Explanation:- as fractional knapsack gives extra liberty to include the object partially which is not
possible with 0/1 knapsack, thus

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

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.

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

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.

View all MCQ's at McqMate.com