Top 150+ Solved Design and Analysis of Algorithms MCQ Questions Answer
Q. What is the source?
a. vertex with no incoming edges
b. vertex with no leaving edges
c. centre vertex
d. vertex with the least weight
Q. Which algorithm is used to solve a maximum flow problem?
a. prim’s algorithm
b. kruskal’s algorithm
c. dijkstra’s algorithm
d. ford-fulkerson algorithm
Q. Does Ford- Fulkerson algorithm use the idea of?
a. naïve greedy algorithm approach
b. residual graphs
c. minimum cut
d. minimum spanning tree
Q. The first step in the naïve greedy algorithm is?
a. analysing the zero flow
b. calculating the maximum flow using trial and error
c. adding flows with higher values
d. reversing flow if required
Q. Under what condition can a vertex combine and distribute flow in any manner?
a. it may violate edge capacities
b. it should maintain flow conservation
c. the vertex should be a source vertex
d. the vertex should be a sink vertex
Q. Which of the following problems is similar to that of a Hamiltonian path problem?
a. knapsack problem
b. closest pair problem
c. travelling salesman problem
d. assignment problem
Q. Who formulated the first ever algorithm for solving the Hamiltonian path problem?
a. martello
b. monte carlo
c. leonard
d. bellman
Q. In what time can the Hamiltonian path problem can be solved using dynamic programming?
a. o(n)
b. o(n log n)
c. o(n2)
d. o(n2 2n)
Q. Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem?
a. karp
b. leonard adleman
c. andreas bjorklund
d. martello
Q. For a graph of degree three, in what time can a Hamiltonian path be found?
a. o(0.251n)
b. o(0.401n)
c. o(0.167n)
d. o(0.151n)
Q. What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
a. o(n!)
b. o(n! * n)
c. o(log n)
d. o(n)