1
MCQ (Single Correct Answer)

### GATE CSE 2015 Set 2

In a connected graph, bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
A
A tree has no bridges
B
A bridge cannot be part of a simple cycle
C
Every edge of a clique with size $\ge 3$ is a bridge (A clique is any complete sub-graph of a graph )
D
A graph with bridges cannot have a cycle
2
Numerical

### GATE CSE 2015 Set 2

The number of onto functions (subjective functions) from set $X = \left\{ {1,2,3,4} \right\}$ to set $Y = \left\{ {a,b,c} \right\}$ is __________________.

Correct Answer is 36
3
Numerical

### GATE CSE 2015 Set 2

Let $X$ and $Y$ denote the sets containing $2$ and $20$ distinct objects respectively and $𝐹$ denote the set of all possible functions defined from $X$ to $Y$. Let $f$ be randomly chosen from $F.$ The probability of $f$ being one-to-one is ________.

Correct Answer is 0.95
4
MCQ (Single Correct Answer)

### GATE CSE 2015 Set 2

Which one of the following well formed formulae is a tautology?
A
$\forall x\,\exists y\,R\left( {x,y} \right) \leftrightarrow \exists y\forall x\,R\left( {x,y} \right)$
B
$\left( {\forall x\left[ {\exists y\,R\left( {x,y} \right) \to S\left( {x,y} \right)} \right]} \right) \to \forall x\exists y\,S\left( {x,y} \right)$
C
$\left[ {\forall x\,\exists y\,\left( {P\left( {x,y} \right)} \right. \to R\left( {x,y} \right)} \right] \leftrightarrow \left[ {\forall x\,\exists y\,\left( {\neg P\left( {x,y} \right)V\,R\left( {x,y} \right)} \right.} \right]$
D
$\forall x\,\forall y\,P\left( {x,y} \right) \to \forall x\forall y\,P\left( {y,x} \right)$

### Paper Analysis of GATE CSE 2015 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization4
Data Structures3
Database Management System4
Digital Logic3
Discrete Mathematics12
Operating Systems4
Programming Languages3
Software Engineering3
Theory of Computation4
Web Technologies1

### EXAM MAP

#### Joint Entrance Examination

JEE Advanced JEE Main

#### Graduate Aptitude Test in Engineering

GATE CSE GATE EE GATE ECE GATE ME GATE CE GATE PI GATE IN