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
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
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
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 incidence matrix and bipartite graph
d) none of the mentioned
View Answer
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
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 directed and undirected
d) none of the mentioned
View Answer
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
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).
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
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
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
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.
- Check Computer Science Books
- Practice Computer Science MCQs
- Check Automata Theory Books
- Apply for Computer Science Internship