Automata Theory Questions and Answers – Node-Cover Problem, Hamilton Circuit Problem

«
»

This set of Automata Theory Questions and Answers for Aptitude test focuses 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
View Answer

Answer: c
Explanation: Vertex cover or Node cover problem, and Hamilton Circuit problem, both are NP complete type of problems.
advertisement

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
View Answer

Answer: d
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: c
Explanation: 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.
advertisement

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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: c
Explanation: 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
View Answer

Answer: a
Explanation: 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).
advertisement

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
View Answer

Answer: d
Explanation: 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
View Answer

Answer: a
Explanation: 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
View Answer

Answer: b
Explanation: 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.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Aptitude test, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn