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

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) 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) Node cover problems & Directed Hamilton Circuit Problem
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.

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

4. An exact cover problem can be represented using:
a) incidence matrix
b) bipartite graph
c) both incidence matrix and bipartite graph
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.

5. For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?
a) tree graphs
b) bipartite graphs
c) all of the mentioned
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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Hamilton circuit problem can have the following version/s as per the input graph:
a) directed
b) undirected
c) both directed and undirected
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.
advertisement

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, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.