1

### GATE CSE 2016 Set 2

Consider a set $U$ of $23$ different compounds in a Chemistry lab. There is a subset $S$ of $U$ of $9$ compounds, each of which reacts with exactly $3$ compounds of $U.$ Consider the following statements:

$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$ Each compound in $U \ S$ reacts with an odd number of compounds.
$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,$ At least one compound in $U \ S$ reacts with an odd number of compounds.
$\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,$ Each compound in $U \ S$ reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE?

A
Only ${\rm I}$
B
Only ${\rm II}$
C
Only ${\rm III}$
D
None
2

### GATE CSE 2016 Set 2

Which one of the following well-formed formulae in predicate calculus is NOT valid?
A
$\left( {\forall xp\left( x \right) \vee \forall xq\left( x \right)} \right) \Rightarrow \left( {\exists x\neg p\left( x \right) \vee \forall xq\left( x \right)} \right)$
B
$\left( {\exists xp\left( x \right) \vee \exists xq\left( x \right)} \right) \Rightarrow \exists x\left( {p\left( x \right) \vee q\left( x \right)} \right)$
C
$\exists x\left( {p\left( x \right) \wedge q\left( x \right)} \right) \Rightarrow \left( {\exists xp\left( x \right) \wedge \exists xq\left( x \right)} \right)$
D
$\forall x\left( {p\left( x \right) \vee q\left( x \right)} \right) \Rightarrow \left( {\forall xp\left( x \right) \vee \forall xq\left( x \right)} \right)$
3
Numerical

### GATE CSE 2016 Set 2

The value of the expression ${13^{99}}$ ($mod$ $17$), in the range $0$ to $16,$ is ______________ .

4

### GATE CSE 2016 Set 2

In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?
A
$LRU$ (Least Recently Used)
B
$OPT$ (Optimal Page Replacement)
C
$MRU$ (Most Recently Used)
D
$FIFO$ (First In First Out)

### Paper Analysis of GATE CSE 2016 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization6
Data Structures5
Database Management System4
Digital Logic3
Discrete Mathematics11
Operating Systems3
Theory of Computation6
General Aptitude10