gs gs101 Intractable Problems - Node-Cover Problem and Hamilton Circuit Problem - Quiz No.1
gs gs101 Automata Theory Quiz
This quiz belongs to book/course code gs gs101 Automata Theory of gs organization. We have 92 quizzes available related to the book/course Automata Theory. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Intractable Problems. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: Which of the given problems are NP-complete?
Node cover problems
Directed Hamilton Circuit Problem
Node cover problems & Directed Hamilton Circuit Problem
None of the mentioned
Question 2: Which of the following problems do not belong to Karp’s 21 NP-complete problems?
Vertex Cover problems
Knapsack
0-1 integer programming
None of the mentioned
Question 3: Which of the following problems were reduced to Knapsack?
Exact Cover
Max Cut
0-1 integer programming
None of the mentioned
Question 4: An exact cover problem can be represented using:
incidence matrix
bipartite graph
both incidence matrix and bipartite graph
none of the mentioned
Question 5: For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?
tree graphs
bipartite graphs
all of the mentioned
none of the mentioned
Question 6: Hamilton circuit problem can have the following version/s as per the input graph:
directed
undirected
both directed and undirected
none of the mentioned
Question 7: Hamilton Circuit problem is a special case of ____________
travelling salesman problem
halting problem
hitting set
none of the mentioned
Question 8: Which of the following cannot solve Hamilton Circuit problem?
DNA Computer
Monte Carlo algorithm
Dynamic programming
None of the mentioned
Question 10: Fibonacci number falls in the category of _________ combinatorics.
Algebric
Enumerative
Analytic
Extremal
Online Quizzes of gs101 Automata Theory
Other Classes Of Problems - Randomized Algorithm - Quiz No.1
gs gs101
Automata Theory Online Quizzes
Push Down Automata - DPDA and Ambiguous Grammars - Quiz No.1
gs gs101
Automata Theory Online Quizzes
