Design And Analysis Of Algorithms Set 16

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 16

Q1 | In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called?
  • bipartite matching
  • cardinality matching
  • augmenting
  • weight matching
Answer: augmenting
Explaination:
a simple path from a free vertex in v to a free vertex in u whose edges alternate between edges not in m and edges in m is called a augmenting path.
Q2 | A matching M is maximal if and only if there exists no augmenting path with respect to M.
  • true
  • false
Answer: true
Explaination:
according to the theorem discovered by the french mathematician claude berge, it means that the current matching is maximal if there is no augmenting path.
Q3 | Which one of the following is an application for matching?
  • proposal of marriage
  • pairing boys and girls for a dance
  • arranging elements in a set
  • finding the shortest traversal path
Answer: pairing boys and girls for a dance
Explaination:
pairing boys and girls for a dance is a traditional example for matching. proposal of marriage is an application of stable marriage problem.
Q4 | Which is the correct technique for finding a maximum matching in a graph?
  • dfs traversal
  • bfs traversal
  • shortest path traversal
  • heap order traversal
Answer: bfs traversal
Explaination:
the correct technique for finding a maximum matching in a bipartite graph is by using a breadth first search(bfs).
Q5 | The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?
  • maximum- mass matching
  • maximum bipartite matching
  • maximum weight matching
  • maximum node matching
Answer: maximum weight matching
Explaination:
the problem is called as maximum weight matching which is similar to a bipartite matching. it is also called as assignment problem.
Q6 | Who was the first person to solve the maximum matching problem?
  • jack edmonds
  • hopcroft
  • karp
  • claude berge
Answer: jack edmonds
Explaination:
jack edmonds was the first person to solve the maximum matching problem in 1965.
Q7 | From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?
  • 5
  • 4
  • 3
  • 2
Answer: 5
Explaination:
one of the solutions of the matching problem is given by a-w,b-v,c-x,d- y,e-z. hence the answer is 5.
Q8 | The worst-case efficiency of solving a problem in polynomial time is?
  • o(p(n))
  • o(p( n log n))
  • o(p(n2))
  • o(p(m log n))
Answer: o(p(n))
Explaination:
the worst-case efficiency of solving an problem in polynomial time is o(p(n)) where p(n) is the polynomial time of input size.
Q9 | Problems that can be solved in polynomial time are known as?
  • intractable
  • tractable
  • decision
  • complete
Answer: tractable
Explaination:
problems that can be solved in polynomial time are known as tractable.
Q10 | The sum and composition of two polynomials are always polynomials.
  • true
  • false
Answer: true
Explaination:
one of the properties of polynomial functions states that the sum and composition of two polynomials are always polynomials.
Q11 |                    is the class of decision problems that can be solved by non- deterministic polynomial algorithms?
  • np
  • p
  • hard
  • complete
Answer: np
Explaination:
np problems are called as non- deterministic polynomial problems. they are a class of decision problems that can be solved using np algorithms.
Q12 | Problems that cannot be solved by any algorithm are called?
  • tractable problems
  • intractable problems
  • undecidable problems
  • decidable problems
Answer: undecidable problems
Explaination:
problems cannot be solved by any algorithm are called undecidable problems. problems that can be solved in polynomial time are called tractable problems.
Q13 | The Euler’s circuit problem can be solved in?
  • o(n)
  • o( n log n)
  • o(log n)
  • o(n2)
Answer: o(n2)
Explaination:
mathematically, the run time of euler’s circuit problem is determined to be o(n2).
Q14 | To which class does the Euler’s circuit problem belong?
  • p class
  • np class
  • partition class
  • complete class
Answer: p class
Explaination:
euler’s circuit problem can be solved in polynomial time. it can be solved in o(n2).
Q15 | Halting problem is an example for?
  • decidable problem
  • undecidable problem
  • complete problem
  • trackable problem
Answer: undecidable problem
Explaination:
halting problem by alan turing cannot be solved by any algorithm. hence, it is undecidable.
Q16 | How many stages of procedure does a non- deterministic algorithm consist of?
  • 1
  • 2
  • 3
  • 4
Answer: 2
Explaination:
a non-deterministic algorithm is a two-stage procedure- guessing stage and verification stage.
Q17 | A non-deterministic algorithm is said to be non-deterministic polynomial if the time- efficiency of its verification stage is polynomial.
  • true
  • false
Answer: true
Explaination:
one of the properties of np class problems states that a non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.
Q18 | How many conditions have to be met if an NP- complete problem is polynomially reducible?
  • 1
  • 2
  • 3
  • 4
Answer: 2
Explaination:
a function t that maps all yes instances of decision problems d1 and d2 and t should be computed in polynomial time are the two conditions.
Q19 | To which of the following class does a CNF-satisfiability problem belong?
  • np class
  • p class
  • np complete
  • np hard
Answer: np complete
Explaination:
the cnf satisfiability problem belongs to np complete class. it deals with boolean expressions.
Q20 | How many steps are required to prove that a decision problem is NP complete?
  • 1
  • 2
  • 3
  • 4
Answer: 2
Explaination:
first, the problem should be np. next, it should be proved that every problem in np is reducible to the problem in question in polynomial time.
Q21 | Which of the following problems is not NP complete?
  • hamiltonian circuit
  • bin packing
  • partition problem
  • halting problem
Answer: halting problem
Explaination:
hamiltonian circuit, bin packing, partition problems are np complete problems. halting problem is an undecidable problem.
Q22 | The choice of polynomial class has led to the development of an extensive theory called
  • computational complexity
  • time complexity
  • problem complexity
  • decision complexity
Answer: computational complexity
Explaination:
an extensive theory called computational complexity seeks to classify problems according to their inherent difficulty.
Q23 | Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
  • branch and bound
  • iterative improvement
  • divide and conquer
  • greedy algorithm
Answer: branch and bound
Explaination:
the hamiltonian path problem can be solved efficiently using branch and bound approach. it can also be solved using a backtracking approach.
Q24 | The problem of finding a path in a graph that visits every vertex exactly once is called?
  • hamiltonian path problem
  • hamiltonian cycle problem
  • subset sum problem
  • turnpike reconstruction problem
Answer: hamiltonian path problem
Explaination:
hamiltonian path problem is a problem of finding a path in a graph that visits every node exactly once whereas hamiltonian cycle problem is finding a cycle in a graph.
Q25 | Hamiltonian path problem is                    
  • np problem
  • n class problem
  • p class problem
  • np complete problem
Answer: np complete problem
Explaination:
hamiltonian path problem is found to be np complete. hamiltonian cycle problem is also an np- complete problem.
Previous Next