The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Hot questions in Discrete Mathematics
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
+3
votes
1
answer
1
relation
Number of relations $S$ over set $\{0,1,2,3 \}$ such that $(x,y) \in S \Rightarrow x = y$
asked
Dec 27, 2017
in
Set Theory & Algebra
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

41.7k
views
relations
+60
votes
6
answers
2
GATE201238
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
asked
Sep 12, 2014
in
Graph Theory
by
gatecse
Boss
(
18.4k
points)

9.3k
views
gate2012
graphtheory
normal
markstoall
counting
+34
votes
10
answers
3
GATE2016126
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

8.4k
views
gate20161
permutationsandcombinations
generatingfunctions
normal
numericalanswers
+19
votes
2
answers
4
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?
asked
Oct 24, 2014
in
Set Theory & Algebra
by
shree
Active
(
3.5k
points)

13.6k
views
settheory&algebra
+35
votes
8
answers
5
GATE2016127
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

6.9k
views
gate20161
permutationsandcombinations
recurrence
normal
numericalanswers
+20
votes
10
answers
6
GATE201846
The number of possible minheaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
asked
Feb 14, 2018
in
Combinatory
by
gatecse
Boss
(
18.4k
points)

7.2k
views
gate2018
permutationsandcombinations
numericalanswers
+52
votes
7
answers
7
GATE2014151
Consider an undirected graph $G$ where selfloops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
asked
Sep 28, 2014
in
Graph Theory
by
jothee
Veteran
(
116k
points)

6.9k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
+12
votes
7
answers
8
GATE20181
Which one of the following is a closed form expression for the generating function of the sequence $\{a_n\}$, where $a_n = 2n +3 \text{ for all } n=0, 1, 2, \dots$? $\frac{3}{(1x)^2}$ $\frac{3x}{(1x)^2}$ $\frac{2x}{(1x)^2}$ $\frac{3x}{(1x)^2}$
asked
Feb 14, 2018
in
Combinatory
by
gatecse
Boss
(
18.4k
points)

5.5k
views
gate2018
generatingfunctions
normal
+45
votes
6
answers
9
GATE2016228
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: Each compound in U \ S reacts with an odd number ... in U \ S reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE? Only I Only II Only III None.
asked
Feb 12, 2016
in
Set Theory & Algebra
by
Akash Kanase
Boss
(
43.6k
points)

4.5k
views
gate20162
settheory&algebra
difficult
sets
+3
votes
5
answers
10
GATE201935
Consider the first order predicate formula $\varphi$: $\forall x [ ( \forall z \: z \mid x \Rightarrow (( z=x) \vee (z=1))) \rightarrow \exists w ( w > x) \wedge (\forall z \: z \mid w \Rightarrow ((w=z) \vee (z=1)))]$ Here $a \mid b$ ... Set of all positive integers $S3:$ Set of all integers Which of the above sets satisfy $\varphi$? S1 and S2 S1 and S3 S2 and S3 S1, S2 and S3
asked
Feb 7
in
Mathematical Logic
by
Arjun
Veteran
(
400k
points)

3.8k
views
gate2019
engineeringmathematics
discretemathematics
mathematicallogic
+33
votes
6
answers
11
GATE2017247
If the ordinary generating function of a sequence $\big \{a_n\big \}_{n=0}^\infty$ is $\large \frac{1+z}{(1z)^3}$, then $a_3a_0$ is equal to ___________ .
asked
Feb 14, 2017
in
Combinatory
by
Arjun
Veteran
(
400k
points)

5.3k
views
gate20172
permutationsandcombinations
generatingfunctions
numericalanswers
normal
+46
votes
7
answers
12
GATE2015139
Consider the operations $\textit{f (X, Y, Z) = X'YZ + XY' + Y'Z'}$ and $\textit{g (X, Y, Z) = X'YZ + X'YZ' + XY}$ Which one of the following is correct? Both $\left\{\textit{f} \right\}$ and $\left\{ \textit{g}\right\}$ are ... Only $\left\{ \textit{g}\right\}$ is functionally complete Neither $\left\{ \textit{f}\right\}$ nor $\left\{\textit{g}\right\}$ is functionally complete
asked
Feb 13, 2015
in
Set Theory & Algebra
by
makhdoom ghaya
Boss
(
41.2k
points)

6.9k
views
gate20151
settheory&algebra
functions
difficult
0
votes
2
answers
13
ISI2019MMA27
A general election is to be scheduled on $5$ days in May such that it is not scheduled on two consecutive days. In how many ways can the $5$ days be chosen to hold the election? $\begin{pmatrix} 26 \\ 5 \end{pmatrix}$ $\begin{pmatrix} 27 \\ 5 \end{pmatrix}$ $\begin{pmatrix} 30 \\ 5 \end{pmatrix}$ $\begin{pmatrix} 31 \\ 5 \end{pmatrix}$
asked
May 7
in
Combinatory
by
Sayan Bose
Loyal
(
6.9k
points)

2.7k
views
isi2019
engineeringmathematics
discretemathematics
permutationsandcombinations
+21
votes
8
answers
14
GATE2017223
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
asked
Feb 14, 2017
in
Graph Theory
by
Madhav
Active
(
1.7k
points)

4.3k
views
gate20172
graphtheory
numericalanswers
degreeofgraph
+51
votes
6
answers
15
GATE2016128
A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$,satisfies the following properties: $f(n)=f(n/2)$ if $n$ is even $f(n)=f(n+5)$ if $n$ is odd Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.
asked
Feb 12, 2016
in
Set Theory & Algebra
by
Sandeep Singh
Loyal
(
7.8k
points)

5.6k
views
gate20161
settheory&algebra
functions
normal
numericalanswers
+1
vote
7
answers
16
GATE201912
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n1)!$ $1$ $\frac{(n1)!}{2}$
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
400k
points)

2.7k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+23
votes
6
answers
17
GATE2016229
The value of the expression $13^{99}\pmod{17}$ in the range $0$ to $16$, is ________.
asked
Feb 12, 2016
in
Combinatory
by
Akash Kanase
Boss
(
43.6k
points)

6.1k
views
gate20162
modulararithmetic
normal
numericalanswers
+33
votes
4
answers
18
GATE2016227
Which one of the following wellformed formulae in predicate calculus is NOT valid ? $(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$ $(\exists x p(x) \vee \exists x q (x)) \implies \exists x (p(x) \vee q (x))$ ... $\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$
asked
Feb 12, 2016
in
Mathematical Logic
by
Akash Kanase
Boss
(
43.6k
points)

5.2k
views
gate20162
mathematicallogic
firstorderlogic
normal
+33
votes
6
answers
19
GATE2017102
Consider the firstorder logic sentence $F:\forall x(\exists yR(x,y))$. Assuming nonempty logical domains, which of the sentences below are implied by $F$? $\exists y(\exists xR(x,y))$ $\exists y(\forall xR(x,y))$ $\forall y(\exists xR(x,y))$ $¬\exists x(\forall y¬R(x,y))$ IV only I and IV only II only II and III only
asked
Feb 14, 2017
in
Mathematical Logic
by
khushtak
Loyal
(
7.7k
points)

5.1k
views
gate20171
mathematicallogic
firstorderlogic
+12
votes
8
answers
20
GATE201830
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between ... then $\mid ij \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
asked
Feb 14, 2018
in
Graph Theory
by
gatecse
Boss
(
18.4k
points)

4.7k
views
gate2018
graphtheory
graphsearch
normal
+3
votes
2
answers
21
GATE20195
Let $U = \{1, 2, \dots , n\}$ Let $A=\{(x, X) \mid x \in X, X \subseteq U \}$. Consider the following two statements on $\mid A \mid$. $\mid A \mid = n2^{n1}$ $\mid A \mid = \Sigma_{k=1}^n k \begin{pmatrix} n \\ k \end{pmatrix}$ Which of the above statements is/are TRUE? Only I Only II Both I and II Neither I nor II
asked
Feb 7
in
Combinatory
by
Arjun
Veteran
(
400k
points)

2.3k
views
gate2019
engineeringmathematics
discretemathematics
permutationsandcombinations
+28
votes
5
answers
22
GATE2016226
A binary relation $R$ on $\mathbb{N} \times \mathbb{N}$ is defined as follows: $(a, b) R(c, d)$ if $a \leq c$ or $b \leq d$. Consider the following propositions: $P:$ $R$ is reflexive. $Q:$ $R$ is transitive. Which one of the following statements is TRUE? Both $P$ and $Q$ are true. $P$ is true and $Q$ is false. $P$ is false and $Q$ is true. Both $P$ and $Q$ are false.
asked
Feb 12, 2016
in
Set Theory & Algebra
by
Akash Kanase
Boss
(
43.6k
points)

4k
views
gate20162
settheory&algebra
relations
normal
+15
votes
3
answers
23
GATE201828
Consider the firstorder logic sentence $\varphi \equiv \exists \: s \: \exists \: t \: \exists \: u \: \forall \: v \: \forall \: w \forall \: x \: \forall \: y \: \psi(s, t, u, v, w, x, y)$ ... than or equal to $3$ There exists no model of $\varphi$ with universe size of greater than $7$ Every model of $\varphi$ has a universe of size equal to $7$
asked
Feb 14, 2018
in
Mathematical Logic
by
gatecse
Boss
(
18.4k
points)

5.8k
views
gate2018
mathematicallogic
normal
firstorderlogic
+19
votes
7
answers
24
GATE2017211
Let $p, q, r$ ... $(\neg p \wedge r) \vee (r \rightarrow (p \wedge q))$
asked
Feb 14, 2017
in
Mathematical Logic
by
khushtak
Loyal
(
7.7k
points)

3.4k
views
gate20172
mathematicallogic
propositionallogic
+4
votes
4
answers
25
GATE201910
Let $G$ be an arbitrary group. Consider the following relations on $G$: $R_1: \forall a , b \in G, \: a R_1 b \text{ if and only if } \exists g \in G \text{ such that } a = g^{1}bg$ $R_2: \forall a , b \in G, \: a R_2 b \text{ if and only if } a= b^{1}$ Which of the above is/are equivalence relation/relations? $R_1$ and $R_2$ $R_1$ only $R_2$ only Neither $R_1$ nor $R_2$
asked
Feb 7
in
Set Theory & Algebra
by
Arjun
Veteran
(
400k
points)

2.2k
views
gate2019
engineeringmathematics
discretemathematics
settheory&algebra
groups
+3
votes
2
answers
26
How many transitive relations are there on a set with n elements if a)n=1 b) n=2 c) n=3
asked
Mar 7, 2017
in
Set Theory & Algebra
by
Sanjay Sharma
Veteran
(
50.7k
points)

5.5k
views
+1
vote
1
answer
27
GATE201938
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimumweight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
400k
points)

2.3k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+19
votes
4
answers
28
GATE201827
Let $N$ be the set of natural numbers. Consider the following sets, $P:$ Set of Rational numbers (positive and negative) $Q:$ Set of functions from $\{0,1\}$ to $N$ $R:$ Set of functions from $N$ to $\{0, 1\}$ $S:$ Set of finite subsets of $N$ Which of the above sets are countable? $Q$ and $S$ only $P$ and $S$ only $P$ and $R$ only $P, Q$ and $S$ only
asked
Feb 14, 2018
in
Set Theory & Algebra
by
gatecse
Boss
(
18.4k
points)

4.2k
views
gate2018
settheory&algebra
countableset
normal
+32
votes
6
answers
29
GATE2014351
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $nk$ $nk+1$
asked
Sep 28, 2014
in
Graph Theory
by
jothee
Veteran
(
116k
points)

4.1k
views
gate20143
graphtheory
graphconnectivity
normal
0
votes
0
answers
30
KPGCETCSE20191
The relational DBMS is constructed on relational principles which are based on l9090 The matrix theory Axiomatic principles Primary key Primary and foreign key relationship
asked
Jul 24
in
Mathematical Logic
by
Arjun
Veteran
(
400k
points)

6
views
kpgcetcse2019
Page:
1
2
3
4
5
6
...
174
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has started
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
All categories
General Aptitude
1.7k
Engineering Mathematics
7.4k
Discrete Mathematics
5.2k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
898
Graph Theory
801
Probability
989
Linear Algebra
686
Calculus
497
Digital Logic
2.9k
Programming & DS
4.9k
Algorithms
4.3k
Theory of Computation
6k
Compiler Design
2k
Operating System
4.2k
Databases
4.1k
CO & Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.4k
Others
1.6k
Admissions
591
Exam Queries
643
Tier 1 Placement Questions
23
Job Queries
72
Projects
23
Follow @csegate
Recent Blog Comments
It was free when I gave them, maybe they made it...
The tests are there but it ain't free. Cost is...
They removed their tests recently, I think it'll...
how did you get Success gateway test series for...
49,721
questions
53,593
answers
185,825
comments
70,878
users