Applications of Pumping Lemma/Pigeonhole principle Online Exam Quiz
Applications of Pumping Lemma/Pigeonhole principle GK Quiz. Question and Answers related to Applications of Pumping Lemma/Pigeonhole principle. MCQ (Multiple Choice Questions with answers about Applications of Pumping Lemma/Pigeonhole principle
An exact cover problem can be represented using:
Options
A : incidence matrix
B : bipartite graph
C : both (a) and (b)
D : none of the mentioned
For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?
Options
A : tree graphs
B : bipartite graphs
C : both (a) and (b)
D : none of the mentioned
If n objects are distributed over m places, and n < m, then some of the places receive:
Options
A : at least 2 objects
B : at most 2 objects
C : no object
D : none of the mentioned
Which of the following can refer a language to be non regular?
Options
A : Pumping Lemma
B : Myphill Nerode
C : Both (a) and (b)
D : None of the mentioned
Which of the following fields may have pigeonhole principle violated?
Options
A : Discrete mathematics
B : Computer Science
C : Quantum Mechanics
D : None of the mentioned
Which of the following is not an application of Pumping Lemma?
Options
A : {0i1i|i>=0}
B : {0ix|i>=0, x?{0, 1}* and |x|<=i}
C : {0n| n is prime}
D : None of the mentioned
Which of the following is not an example of counting argument?
Options
A : Pigeonhole principle
B : Dirichlet's drawer principle
C : Dirichlet's box principle
D : None of the mentioned
Which of the following problems do not belong to Karp's 21 NP-complete problems?
Options
A : Vertex Cover problems
B : Knapsack
C : 0-1 integer programming
D : None of the mentioned
Which of the following problems were reduced to Knapsack?
Options
A : Exact Cover
B : Max Cut
C : 0-1 integer programming
D : None of the mentioned
Which of the given problems are NP-complete?
Options
A : Node cover problems
B : Directed Hamilton Circuit Problem
C : Both (a) and (b)
D : None of the mentioned
Ambiguous Grammar more Online Exam Quiz
CFG-Eliminating Useless Symbols
Deterministic Finite Automata-Introduction and Definition
Finding Patterns in Text,Algebric Laws and Derivatives