102
84.2k

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

151.

The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm.

A. true
B. false
Answer» B. false
Explanation: the number of iterations involved in bellmann ford algorithm is more than that of dijkstra’s algorithm.
152.

Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V.

A. true
B. false
Answer» A. true
Explanation: the equality d[u]=delta(s,u) holds good when vertex u is added to set s and this equality is maintained thereafter by the upper bound property.
153.

Bellmann ford algorithm provides solution for                          problems.

A. all pair shortest path
B. sorting
C. network flow
D. single source shortest path
Answer» D. single source shortest path
Explanation: bellmann ford algorithm is used for finding solutions for single source shortest path problems. if the graph has no negative cycles that are reachable from the source then the algorithm produces the shortest paths and their weights.
154.

Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.

A. true
B. false
Answer» A. true
Explanation: bellmann ford algorithm returns true if the graph does not have any negative weight cycles and returns false when the graph has negative weight cycles.
155.

How many solution/solutions are available for a graph having negative weight cycle?

A. one solution
B. two solutions
C. no solution
D. infinite solutions
Answer» C. no solution
Explanation: if the graph has any negative weight cycle then the algorithm indicates that no solution exists for that graph.
156.

What is the running time of Bellmann Ford Algorithm?

A. o(v)
B. o(v2)
C. o(elogv)
D. o(ve)
Answer» D. o(ve)
Explanation: bellmann ford algorithm runs in time o(ve), since the initialization takes o(v) for each of v-1 passes and the for loop in the algorithm takes o(e) time. hence the total time taken by the algorithm is o(ve).
157.

How many times the for loop in the Bellmann Ford Algorithm gets executed?

A. v times
B. v-1
C. e
D. e-1
Answer» B. v-1
Explanation: the for loop in the bellmann ford algorithm gets executed for v-1 times. after making v-1 passes, the algorithm checks for a negative weight cycle and returns appropriate boolean value.
158.

Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm.

A. true
B. false
Answer» A. true
Explanation: the running time of bellmann ford algorithm is o(ve) whereas dijikstra’s algorithm has running time of only o(v2).
159.

What is the basic principle behind Bellmann Ford Algorithm?

A. interpolation
B. extrapolation
C. regression
D. relaxation
Answer» D. relaxation
Explanation: relaxation methods which are also called as iterative methods in which an approximation to the correct distance is replaced progressively by more accurate values till an optimum solution is found.
160.

Bellmann Ford Algorithm can be applied for                            

A. undirected and weighted graphs
B. undirected and unweighted graphs
C. directed and weighted graphs
D. all directed graphs
Answer» C. directed and weighted graphs
Explanation: bellmann ford algorithm can be applied for all directed and weighted graphs. the weight function in the graph may either be positive or negative.
161.

Bellmann Ford algorithm was first proposed by                  

A. richard bellmann
B. alfonso shimbe
C. lester ford jr
D. edward f. moore
Answer» B. alfonso shimbe
Explanation: alfonso shimbe proposed bellmann ford algorithm in the year 1955. later it was published by richard bellmann in 1957 and lester ford jr in the year 1956. hence it is called bellmann ford algorithm.
162.

Bellmann Ford Algorithm is an example for                          

A. dynamic programming
B. greedy algorithms
C. linear programming
D. branch and bound
Answer» A. dynamic programming
Explanation: in bellmann ford algorithm the shortest paths are calculated in bottom up manner which is similar to other dynamic programming problems.
163.

A graph is said to have a negative weight cycle when?

A. the graph has 1 negative weighted edge
B. the graph has a cycle
C. the total weight of the graph is negative
D. the graph has 1 or more negative weighted edges
Answer» C. the total weight of the graph is negative
Explanation: when the total weight of the graph sums up to a negative number then the graph is said to have a negative weight cycle. bellmann ford algorithm provides no solution for such graphs.
164.

Floyd Warshall’s Algorithm is used for solving                          

A. all pair shortest path problems
B. single source shortest path problems
C. network flow problems
D. sorting problems
Answer» A. all pair shortest path problems
Explanation: floyd warshall’s algorithm is used for solving all pair shortest path problems. it means the algorithm is used for finding the shortest paths between all pairs of vertices in a graph.
165.

Floyd Warshall’s Algorithm can be applied on                      

A. undirected and unweighted graphs
B. undirected graphs
C. directed graphs
D. acyclic graphs
Answer» C. directed graphs
Explanation: floyd warshall algorithm can be applied in directed graphs. from a given directed graph, an adjacency matrix is framed and then all pair shortest path is computed by the floyd warshall algorithm.
166.

What is the running time of the Floyd Warshall Algorithm?

A. big-oh(v)
B. theta(v2)
C. big-oh(ve)
D. theta(v3)
Answer» D. theta(v3)
Explanation: the running time of the floyd warshall algorithm is determined by the triply nested for loops. since each execution of the for loop takes o(1) time, the algorithm runs in time theta(v3).
167.

What approach is being followed in Floyd Warshall Algorithm?

A. greedy technique
B. dynamic programming
C. linear programming
D. backtracking
Answer» B. dynamic programming
Explanation: floyd warshall algorithm follows dynamic programming approach because the all pair shortest paths are computed in bottom up manner.
168.

Floyd Warshall Algorithm can be used for finding                            

A. single source shortest path
B. topological sort
C. minimum spanning tree
D. transitive closure
Answer» D. transitive closure
Explanation: one of the ways to compute the transitive closure of a graph in theta(n3) time is to assign a weight of 1 to each edge of e and then run the floyd warshall algorithm.
169.

What procedure is being followed in Floyd Warshall Algorithm?

A. top down
B. bottom up
C. big bang
D. sandwich
Answer» B. bottom up
Explanation: bottom up procedure is being used to compute the values of the matrix elements dij(k). the input is an n x n matrix.
170.

Floyd- Warshall algorithm was proposed by                          

A. robert floyd and stephen warshall
B. stephen floyd and robert warshall
C. bernad floyd and robert warshall
D. robert floyd and bernad warshall
Answer» A. robert floyd and stephen warshall
Explanation: floyd- warshall algorithm was proposed by robert floyd in the year 1962.
171.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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.