# 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