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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exam Category
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.
Recent activity by Warrior
User Warrior
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User Warrior
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
2
answers
1
GATE200625
Let S = {1, 2, 3,........, m}, m >3. Let X1.........Xn be subsets of S each of size 3. Define a function f from S to the set of natural numbers as, f(i) is the number of sets Xj that contain the element i. That is $f(i)=\left  \left\{j \mid i\in X_j \right\} \right$ then $ \sum_{i=1}^{m} f(i)$ is: 3m 3n 2m+1 2n+1
commented
9 hours
ago
in
Set Theory & Algebra

741
views
gate2006
settheory&algebra
normal
functions
2
answers
2
GATE200813, ISRO201636
If $L$ and $\bar L$ are recursively enumerable then $L$ is regular contextfree contextsensitive recursive
commented
11 hours
ago
in
Theory of Computation

1.6k
views
gate2008
theoryofcomputation
easy
isro2016
recursiveandrecursivelyenumerablelanguages
2
answers
3
GATE20072
Let $S$ be a set of $n$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $S$ are: $n$ and $n$ $n^2$ and $n$ $n^2$ and $0$ $n$ and $1$
commented
Oct 26
in
Set Theory & Algebra

969
views
gate2007
settheory&algebra
normal
relations
2
answers
4
ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
commented
Oct 23
in
Graph Theory

387
views
isi2016
graphtheory
trees
2
answers
5
GATE2013_26
The line graph $L(G)$ of a simple graph $G$ is defined as follows: There is exactly one vertex $v(e)$ in $L(G)$ for each edge $e$ in $G$. For any two edges $e$ and $e'$ in $G$, $L(G)$ has an edge between $v(e)$ and $v(e')$, if and only if $e$ and $e'$ ... . (S) The line graph of a tree is a tree. (A) P only (B) P and R only (C) R only (D) P, Q and S only
comment edited
Oct 23
in
Graph Theory

1.5k
views
gate2013
graphtheory
normal
linegraph
2
answers
6
GATE19903vi
Answer the following: Which of the following graphs is/are planner? (see Fig. 2)
commented
Oct 23
in
Graph Theory

280
views
gate1989
normal
graphtheory
graphplanarity
5
answers
7
GATE20092
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. 2 3 n1 n
commented
Oct 23
in
Graph Theory

1.3k
views
gate2009
graphtheory
graphcoloring
normal
2
answers
8
TIFR2017B1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$
comment reshown
Oct 23
in
Graph Theory

311
views
tifr2017
graphtheory
graphcoloring
2
answers
9
TIFR2013B1
Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum numbers of colours ... \chi (G)\leq a(G)$ $a(G)\geq n/\chi (G)$ $a(G)\leq n/\chi (G)$ None of the above.
answered
Oct 21
in
Graph Theory

325
views
tifr2013
graphtheory
graphcoloring
5
answers
10
GATE200477
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is 2 3 4 5
commented
Oct 21
in
Graph Theory

974
views
gate2004
graphtheory
graphcoloring
easy
4
answers
11
GATE2012_26
Which of the following graphs is isomorphic to
commented
Oct 20
in
Graph Theory

801
views
gate2012
graphtheory
graphisomorphism
normal
5
answers
12
GATE1999_5
Let $G$ be a connected, undirected graph. A cut in $G$ is a set of edges whose removal results in $G$ being broken into two or more components, which are not connected with each other. The size of a cut is called its cardinality. A min ... connected undirected graph $G$ with $n$ vertices has a mincut of cardinality $k$, then $G$ has at least $(nk/2)$ edges
commented
Oct 20
in
Graph Theory

527
views
gate1999
graphtheory
graphconnectivity
normal
2
answers
13
GATE2005IT56
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is 4 7 23 99
commented
Oct 16
in
Graph Theory

1.2k
views
gate2005it
graphtheory
graphconnectivity
normal
3
answers
14
CMI2011A07
Let $G=(V, E)$ be a graph. Define $\bar{G}$ to be $(V, \bar{E})$, where for all $u, \: v \: \in V \: , (u, v) \in \bar{E}$ if and only if $(u, v) \notin E$. Then which of the following is true? $\bar{G}$ is ... $\bar{G}$ is connected if $G$ is not connected. At least one of $G$ and $\bar{G}$ connected. $G$ is not connected or $\bar{G}$ is not connected
commented
Oct 16
in
Graph Theory

202
views
cmi2011
graphtheory
graphconnectivity
3
answers
15
GATE20152_50
In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is true? A tree has no bridges A bridge cannot be part of a simple cycle Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph) A graph with bridges cannot have cycle
commented
Oct 15
in
Graph Theory

1.3k
views
gate20152
graphtheory
graphconnectivity
easy
2
answers
16
GATE20021.25, ISRO200830, ISRO20166
commented
Oct 15
in
Graph Theory

2.7k
views
gate2002
graphtheory
easy
isro2008
isro2016
graphconnectivity
3
answers
17
GATE200673
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{n/2}$ $\frac{2^{n}}{n}$
commented
Oct 15
in
Graph Theory

1k
views
gate2006
graphtheory
normal
graphconnectivity
6
answers
18
GATE200340
A graph $G=(V,E)$ satisfies $E \leq 3 V  6$. The mindegree of $G$ is defined as $\min_{v\in V}\left\{degree (v)\right \}$. Therefore, mindegree of $G$ cannot be 3 4 5 6
answered
Oct 15
in
Graph Theory

1.3k
views
gate2003
graphtheory
normal
degreeofgraph
3
answers
19
GATE200671
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of vertices of degree zero in $G$ is: $1$ $n$ $n + 1$ $2^n$
commented
Oct 15
in
Graph Theory

1.9k
views
gate2006
graphtheory
normal
degreeofgraph
4
answers
20
TIFR2010B36
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices? Exactly seven edges leave every vertex. Exactly seven edges leave some vertex. Some vertex has at least seven edges leaving it. The number of edges coming out of vertex is odd. None of the above.
commented
Oct 12
in
Graph Theory

476
views
tifr2010
graphtheory
degreeofgraph
4
answers
21
GATE200672
The $2^n$ vertices of a graph G corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The maximum degree of a vertex in G is: $\binom{n/2}{2}2^{n/2}$ $2^{n2}$ $2^{n3}\times 3$ $2^{n1}$
answered
Oct 12
in
Graph Theory

1.2k
views
gate2006
graphtheory
normal
degreeofgraph
3
answers
22
TIFR2017B12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n1)}{2}$
commented
Oct 11
in
Graph Theory

501
views
tifr2017
graphtheory
counting
5
answers
23
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
answered
Oct 11
in
Graph Theory

3.7k
views
gate2012
graphtheory
normal
markstoall
counting
3
answers
24
GATE200829
Let $X$ be a random variable following normal distribution with mean $+1$ and variance $4$. Let $Y$ be another normal variable with mean $1$ and variance unknown. If $P (X ≤ 1) = P (Y ≥ 2)$ , the standard deviation of $Y$ is $3$ $2$ $\sqrt{2}$ $1$
commented
Oct 8
in
Probability

1.6k
views
gate2008
randomvariable
normaldistribution
probability
normal
2
answers
25
GATE200512, ISRO200964
Let $f(x)$ be the continuous probability density function of a random variable $x$, the probability that $a < x \leq b$, is : $f(ba)$ $f(b)  f(a)$ $\int\limits_a^b f(x) dx$ $\int\limits_a^b xf (x)dx$
comment edited
Oct 8
in
Probability

1.2k
views
gate2005
probability
randomvariable
easy
isro2009
2
answers
26
GATE200618
We are given a set $X = \{X_1,........X_n\}$ where $X_i=2^i$. A sample $S\subseteq X$ is drawn by selecting each $X_i$ independently with probability $P_i = \frac{1}{2}$ . The expected value of the smallest number in sample $S$ is: $\frac{1}{n}$ $2$ $\sqrt n$ $n$
commented
Oct 5
in
Probability

639
views
gate2006
probability
expectation
normal
2
answers
27
TIFR2014A17
A fair dice (with faces numbered $1, . . . , 6$) is independently rolled repeatedly. Let $X$ denote the number of rolls till an even number is seen and let $Y$ denote the number of rolls till $3$ is seen. Evaluate $E(Y X = 2)$. $6\frac{5}{6}$ $6$ $5\frac{1}{2}$ $6\frac{1}{3}$ $5\frac{2}{3}$
commented
Oct 5
in
Probability

340
views
tifr2014
expectation
1
answer
28
TIFR2012B7
A bag contains $16$ balls of the following colors: 8 red, 4 blue, 2 green, 1 black, and 1 white. Anisha picks a ball randomly from the bag, and messages Babu its color using a string of zeros and ones. She replaces the ball in the bag, ... the minimum expected length of the message she has to convey to Babu per experiment? $3/2$ $\log 5$ $15/8$ $31/16$ $2$
commented
Oct 5
in
Probability

236
views
tifr2012
probability
expectation
2
answers
29
TIFR2011A6
Assume that you are flipping a fair coin, i.e. probability of heads or tails is equal. Then the expected number of coin flips required to obtain two consecutive heads for the first time is. 4 3 6 10 5
commented
Oct 3
in
Probability

379
views
tifr2011
probability
expectation
4
answers
30
GATE200552
A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is: $\frac{1}{2^n}$ $1  \frac{1}{n}$ $\frac{1}{n!}$ $1  \frac{1}{2^n}$
commented
Oct 3
in
Probability

648
views
gate2005
probability
binomialdistribution
easy
2
answers
31
GATE2006IT22
When a coin is tossed, the probability of getting a Head is $p, 0 < p < 1$. Let $N$ be the random variable denoting the number of tosses till the first Head appears, including the toss where the Head appears. Assuming that successive tosses are independent, the expected value of $N$ is $1/p$ $1/(1  p)$ $1/p^2$ $1/(1  p^2)$
answered
Oct 2
in
Probability

810
views
gate2006it
probability
binomialdistribution
expectation
normal
1
answer
32
Sheldon Ross chapter 4 Random variables Qno72
answer selected
Sep 30
in
Probability

83
views
probability
1
answer
33
Sheldon Ross chapter#3 Qno45
A set of k coupons, each of which is independently a type j coupon with probability pj , from j=1 to n ∑ pj = 1, is collected. Find the probability that the set contains either a type i or a type j coupon.
commented
Sep 30
in
Probability

62
views
probability
2
answers
34
Practice
All Conflict serializable schedule are also view serializable but reverse is not true . True or False
commented
Sep 30
in
Databases

53
views
databases
view_serializable
8
answers
35
GATE2012_33
Suppose a fair sixsided die is rolled once. If the value on the die is 1, 2, or 3, the die is rolled a second time. What is the probability that the sum total of values that turn up is at least 6? $10/21$ $5/12$ $2/3$ $1/6$
answered
Sep 26
in
Probability

2.2k
views
gate2012
probability
conditionalprobability
bayestheorem
normal
2
answers
36
GATE2006IT1
In a certain town, the probability that it will rain in the afternoon is known to be 0.6. Moreover, meteorological data indicates that if the temperature at noon is less than or equal to 25°C, the probability that it will rain in the afternoon is 0.4. ... it will rain in the afternoon on a day when the temperature at noon is above 25°C? 0.4 0.6 0.8 0.9
answer edited
Sep 25
in
Probability

551
views
gate2006it
probability
normal
6
answers
37
GATE200724
Suppose we uniformly and randomly select a permutation from the 20! permutations of 1, 2, 3 ... ,20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation? $\frac{1}{2} $ $\frac{1}{10}$ $\frac{9!}{20!}$ None of these
commented
Sep 25
in
Probability

1.7k
views
gate2007
probability
easy
2
answers
38
GATE1996_2.7
The probability that top and bottom cards of a randomly shuffled deck are both aces is $\frac{4}{52} \times \frac{4}{52}$ $\frac{4}{52} \times \frac{3}{52}$ $\frac{4}{52} \times \frac{3}{51}$ $\frac{4}{52} \times \frac{4}{51}$
commented
Sep 25
in
Probability

332
views
gate1996
probability
easy
4
answers
39
GATE2014348
Let $S$ be a sample space and two mutually exclusive events $A$ and $B$ be such that $A \cup B = S$. If $P(.)$ denotes the probability of the event, the maximum value of $P(A)P(B)$ is_____.
commented
Sep 23
in
Probability

839
views
gate20143
probability
numericalanswers
normal
3
answers
40
GATE2014248
The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______ .
answered
Sep 23
in
Probability

931
views
gate20142
probability
numericalanswers
normal
28,947
questions
36,793
answers
91,077
comments
34,690
users