Automata Theory Questions and Answers for Aptitude test on “Node-Cover Problem, Hamilton Circuit Problem”.
1. Which of the given problems are NP-complete?
a) Node cover problems
b) Directed Hamilton Circuit Problem
c) Both (a) and (b)
d) None of the mentioned
Answer: c
Clarification: Vertex cover or Node cover problem, and Hamilton Circuit problem, both are NP complete type of problems.
2. Which of the following problems do not belong to Karp’s 21 NP-complete problems?
a) Vertex Cover problems
b) Knapsack
c) 0-1 integer programming
d) None of the mentioned
Answer: d
Clarification: There exists a set of 21 problems that are NP-complete and the set is called Karp’s 21 NP-complete problems.
3. Which of the following problems were reduced to Knapsack?
a) Exact Cover
b) Max Cut
c) 0-1 integer programming
d) None of the mentioned
Answer: a
Clarification: Exact cover is a decision problem in computer science to determine if an exact cover exists.
4. An exact cover problem can be represented using:
a) incidence matrix
b) bipartite graph
c) both (a) and (b)
d) none of the mentioned
Answer: c
Clarification: The relation ‘contains’ can be represented using a bipartite graph. The vertices of the graph can be divided into two disjoint sets, one representing the subset S and the other representing the elements of P and one edge for each subset in S;each node is included in exactly one of the edges forming the cover.
5. For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?
a) tree graphs
b) bipartite graphs
c) both (a) and (b)
d) none of the mentioned
Answer: a
Clarification: For bipartite graphs, Konigs theorem allows the bipartite vertex problem to be solved in polynomial time.
6. Hamilton circuit problem can have the following version/s as per the input graph:
a) directed
b) undirected
c) both (a) and (b)
d) none of the mentioned
Answer: c
Clarification: Hamilton circuit problem is a problem determining whether a Hamiltonian path(a path in an undirected or directed graph that visits each vertex exactly once) exists in a graph(directed or undirected).
7. Hamilton Circuit problem is a special case of ____________
a) travelling salesman problem
b) halting problem
c) hitting set
d) none of the mentioned
Answer: a
Clarification: Hamilton circuit problem is a special case of travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
8. Which of the following cannot solve Hamilton Circuit problem?
a) DNA Computer
b) Monte Carlo algorithm
c) Dynamic programming
d) None of the mentioned
Answer: d
Clarification: Using Inclusion-exclusion principle, Andreas showed how to solve Hamilton Circuit problem in arbitrary n-vertex graphs by a Monte Carlo algorithm in time O(1.657n).
9. State true or false:
Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.
a) true
b) false
Answer: a
Clarification: Handshaking lemma states that ‘Every finite undirected graph has an even number of vertices with odd degree.
10. Fibonacci number falls in the category of _________ combinatorics.
a) Algebric
b) Enumerative
c) Analytic
d) Extremal
Answer: b
Clarification: Enumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. Fibonacci series is a basic example of Enumerative Combinatorics.