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
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 questions tagged tifr2016
+2
votes
1
answer
1
TIFR2016B15
Let $G$ be an undirected graph. For a pair $(x, y)$ of distinct vertices of $G$, let $\mathsf{mincut}(x, y)$ be the least number of edges that should be delted from $G$ so that the resulting graph has no $xy$ path. Let $a, b, c$ be three vertices ... and iv are possible but neither ii nor iii ii and iv are possible but neither i not iii iii and iv are possible but neither i nor ii
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
112k
points)

106
views
tifr2016
+4
votes
1
answer
2
TIFR2016B14
Consider a family $\mathcal{F}$ of subsets of $\{1, 2, \dots , n\}$ such that for any two distinct sets $A$ and $B$ in $\mathcal{F}$ we have: $A \subset B$ or $ B \subset A$ or $A \cap B = \emptyset$. Which of the following statements is TRUE? (Hint: what does the ... mid \leq 2^{n1}$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n1}$ None of the above
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
112k
points)

102
views
tifr2016
+2
votes
1
answer
3
TIFR2016B13
An undorected graph $G = (V, E)$ is said to be $k$colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we have $c(u) \neq c(v)$. Which of the following statements is ... \Delta$ is the maximum degree in $G$ There is a polynomial time algorithm to check if $G$ is 2colourable If $G$ has no triangle then it is 3colourable
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
112k
points)

47
views
tifr2016
+5
votes
1
answer
4
TIFR2016B12
A computer program computes a function $\: f \: \{0, 1\}^* \times \{0, 1\}^* \rightarrow \{0, 1\}^*$. Suppose $f(a, b)$ ahs length $\mid b \mid ^2$, where $\mid a \mid$ and $\mid b \mid$ are the lengths of $a$ and $b$. Suppose, using this program, the following computation is ... ; t \leq n^2$ $n^2 < t \leq n^{\log_2 n}$ $ n^{\log_2 n} < t \leq 2^{(2n)}$ $2^{(2n)} < t$
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
112k
points)

65
views
tifr2016
+4
votes
0
answers
5
TIFR2016B11
Let $n \geq 4$ be an integer. Regard the set $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the following undirected graph $H$. $$ V(H) = \{S \subseteq \mathbb{R}^n : \: S \text{ is a basis for } \mathbb{ ... ? $H$ has an inifinite number of vertices The diameter of $H$ is infinite $H$ is conneceted $H$ contains an infinite clique $H$ contains an infinite independent set
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
112k
points)

57
views
tifr2016
+3
votes
1
answer
6
TIFR2016B10
A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $I \subseteq V(G)$ such that no edge has both its endpoints in $I$. Which of the following is TRUE of every ... \: \mid E(G)\mid /2$ $\mid C \mid \: \: \geq \: \: \mid V(G)\mid /2$ $C$ intersects every independent set
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
112k
points)

64
views
tifr2016
+5
votes
1
answer
7
TIFR2016B9
Which of the following graphs DOES NOT have an Eulerian circuit? (Recall that an Eulerian circuit in an undirected graph is a walk in the graph that starts at a vertex ans returns to the vertex after tracelling on each edge exactly once.) $K_{9, 9}$ $K_{8, 8}$ $K_{12, 12}$ $K_9$ The graph $G$ on vertex ... G) = \{ \{i, j\} : 1 \leq i < j \leq 5 \: or \: 5 \leq i < j \leq 9 \}.$$
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
112k
points)

149
views
tifr2016
discretemathematics
graphtheory
eulergraph
normal
+3
votes
1
answer
8
TIFR2016B8
Consider the following language $$\mathsf{PRIMES} = \Biggl\{ \underbrace{111 \dots 11}_{p \: \text{ times} } : \: p \: \text{ is prime } \Biggl\}$$ Then, which of the following is TRUE? $\mathsf{PRIMES}$ is regular $\mathsf{PRIMES}$ is undecidable ... }$ is decidable in polynomial time $\mathsf{PRIMES}$ is context free but not regular $\mathsf{PRIMES}$ is NPcomplete and P $\neq$ NP
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
112k
points)

77
views
tifr2016
decidability
pnpnpcnph
+2
votes
0
answers
9
TIFR2016B6
A subset $X$ of $\mathbb{R}^n$ is convex if for all $x, y \in X$ and all $\lambda \in (0, 1)$, we have $\lambda x + (1 \lambda)y \in X$. If $X$ is a convex set, which of the following statements is necessarily TRUE? For every $ x \in X$ there exist $y, z \in X \ ... \dots + x_n)/n \in X$ If $x \in X$, then $\lambda x \in X$ for all scalars $\lambda$ If $x, y \in X$, then $xy \in X$
asked
Dec 28, 2016
in
Others
by
jothee
Veteran
(
112k
points)

32
views
tifr2016
+5
votes
1
answer
10
TIFR2016B5
Consider the recursive function $\mathsf{mc91}$. int mc91(int n) { print n if (n > 100) { return n10; } else { return mc91(mc91(n+11)); } } Let $\mathsf{Out}=\{n : \text{ there is an } x \in \{0, 1, \dots , 100 \} \text{ such that } n \text{ is one of the integers printed by } ... 101 \}$ $\{ n: 0 \leq n \leq 110 \}$ $\{ n: 0 \leq n \leq 111 \}$ $\{ n: 0 \leq n < + \infty \}$
asked
Dec 28, 2016
in
Others
by
jothee
Veteran
(
112k
points)

76
views
tifr2016
+11
votes
2
answers
11
TIFR2016B4
In the following, $A$ stands for a set of apples, and $S(x, y)$ stands for "$x$ is sweeter than $y$. Let $$\Psi \equiv \exists x : x \in A$$ $$\Phi \equiv \forall x \in A : \exists y \in A : S(x, y).$$ Which of the following statements implies that there are infinitely many apples ( ... A : \neg S(x, x)] \wedge [\forall x, y, z \in A : S(x, y) \wedge S(y, z) \rightarrow s(x, z)]$
asked
Dec 28, 2016
in
Mathematical Logic
by
jothee
Veteran
(
112k
points)

470
views
tifr2016
mathematicallogic
firstorderlogic
+2
votes
1
answer
12
TIFR2016B3
Assume $P \neq NP$. Which of the following is not TRUE? 2SAT in NP 2SAT in coNP 3SAT is polynmialtime reducible to 2SAT 4SAT is polynmialtime reducible to 3SAT 2SAT in P
asked
Dec 28, 2016
in
Others
by
jothee
Veteran
(
112k
points)

49
views
tifr2016
pnpnpcnph
3sat
2sat
+2
votes
1
answer
13
TIFR2016B2
Which language class has the following properties? $\quad$ It is closed under union and intersection but not complement. Regular language Contextfree language Recursive language Recursively enumerable language Languages that are not recursively enumerable
asked
Dec 28, 2016
in
Others
by
jothee
Veteran
(
112k
points)

61
views
tifr2016
theoryofcomputation
closureproperty
+2
votes
2
answers
14
TIFR2016B1
A Boolean formula is said to be a $tautology$ if it evaluates to TRUE for all assignments to its variables. Which one of the following is NOT a tautology? $(( p \vee q) \wedge (r \vee s)) \Rightarrow (( p \wedge r) \vee q \vee s)$ $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ... ( r \vee s)) \Rightarrow ( p \vee q \vee s)$ $(( p \vee q ) \wedge ( r \vee s)) \Rightarrow ( p \vee q)$
asked
Dec 28, 2016
in
Digital Logic
by
jothee
Veteran
(
112k
points)

67
views
tifr2016
propositionallogic
+11
votes
3
answers
15
TIFR2016A15
In a tournament with 7 teams, each team plays one match with every other team. For each match, the team earns two points if it wins, one point if it ties, and no points if it loses. At the end of all matches, the teams are ordered in the descending order of ... is the minimum total number of points a team must earn in order to be guaranteed a place in the next round? 13 12 11 10 9
asked
Dec 28, 2016
in
Combinatory
by
jothee
Veteran
(
112k
points)

321
views
tifr2016
permutationsandcombinations
discretemathematics
normal
+2
votes
3
answers
16
TIFR2016A14
A $diagonal$ in a polygon is a straight line segment that connects two nonadjacent vertices, and is contained in the interior of the polygon (except for its points). Two such diagonals are said to cross if they have a point in common in the interior of the polygon. In one such ... be determined from the information given $\frac{n}{2}2$ $\frac{n}{4}1$ $n4$ $n^2  9.5 n +22$
asked
Dec 28, 2016
in
Others
by
jothee
Veteran
(
112k
points)

108
views
tifr2016
graphtheory
generalaptitude
+3
votes
3
answers
17
TIFR2016A13
Let $n \geq 2$ be any integer. Which of the following statements is not necessarily true? $\begin{pmatrix} n \\ i \end{pmatrix} = \begin{pmatrix} n1 \\ i \end{pmatrix} + \begin{pmatrix} n1 \\ i1 \end{pmatrix}, \text{ where } 1 \leq i \leq n1$ $n!$ divides the product of ... \end{pmatrix}$, for all $ i \in \{1, 2, \dots , n1\}$ If $n$ is an odd prime, then $n$ divides $2^{n1} 1$
asked
Dec 28, 2016
in
Others
by
jothee
Veteran
(
112k
points)

104
views
tifr2016
binomialtheorem
+3
votes
1
answer
18
TIFR2016A11
In one of the islands that his travels took him to, Gulliver noticed that the probability that a (uniformly) randomly chosen inhabitant has height at least 2 meters is 0.2. Also, 0.2 is the probability that a a (uniformly) randomly chosen inhabitant has height at ... 2$ Which of the above statements is necessarily true? ii only iii only i, ii and iii ii and iii only None of the above
asked
Dec 28, 2016
in
Others
by
jothee
Veteran
(
112k
points)

54
views
tifr2016
probability
+2
votes
2
answers
19
TIFR2016A10
Consider the sequence $\langle s_n : n \geq 0 \rangle$ defined as follows: $s_0=0, s_1=1, s_2=1$, and $s_n = s_{n1} +s_{n2}+s_{n3}$, for $n \geq 3$. Which of the following statements is FALSE? $s_{4k}$ is even, for any $ k \geq 0$ $s_{4k+1}$ is odd, ... odd, for any $ k \geq 0$ $s_n$ is a multople of 3, for only finitely many values of $n$ $s_{4k+3}$ is even, for any $ k \geq 0$
asked
Dec 27, 2016
in
Others
by
jothee
Veteran
(
112k
points)

70
views
tifr2016
+2
votes
3
answers
20
TIFR2016A9
Suppose a rectangular farm has area 100 square meters. The lengths of its sides are not known. It is known, however, that all the edges are at least 2 meters in length. Which of the following statements about the rectangle's perimeter $p$ (in meters) ... configuration $p$ can take all values between 55 and 60 $p$ can be 70 for some configuration $p$ can be 39 for some configuration
asked
Dec 27, 2016
in
Others
by
jothee
Veteran
(
112k
points)

112
views
tifr2016
+8
votes
3
answers
21
TIFR2016A8
Let $A$ and $B$ be finite sets such that $A \subseteq B$. Then, what is the value of the expression: $$\Sigma_{C:A \subseteq C \subseteq B} (1)^{\mid C \setminus A \mid,}$$ Where $C \setminus A=\{x \in C : x \notin A \}$? Always 0 Always 1 0 if $A=B$ and 1 otherwise 1 if $A=B$ and 0 otherwise Depends on the soze of the universe
asked
Dec 27, 2016
in
Set Theory & Algebra
by
jothee
Veteran
(
112k
points)

252
views
tifr2016
settheory&algebra
sets
+3
votes
1
answer
22
TIFR2016A7
Let $S$ be the $4 \times 4$ square grid $\{(x, y): x, y \in \{0, 1, 2, 3\} \}$. A $monotone \: \: path$ in this grid starts at $(0, 0)$ and at each step either moves one unit up or one unit right. For example, fromthe point $(x, y)$ one can in one ... )$ bt $z$. How many distinct monotone paths are there to reach point $(3, 3)$ starting from $(0, 0)$? $2z+6$ $3z+6$ $2z+8$ $3z+8$ $3z+4$
asked
Dec 27, 2016
in
Others
by
jothee
Veteran
(
112k
points)

67
views
tifr2016
permutationsandcombinations
dynamicprogramming
+2
votes
1
answer
23
TIFR2016A6
Which of the following statements about the eigen values of $I_n$, the $n \times n$ identity matrix (over complex numbers), is true? The eigen values are $1, \omega, \omega^2, \dots , \omega^{n1}$, where $\omega$ is a primitive $n$th root of unity The only eigen ... values, but there are no other eigen values The eigen values are 1$, 1/2, 1/3, \dots , 1/n$ The only eigen value is 1
asked
Dec 26, 2016
in
Others
by
jothee
Veteran
(
112k
points)

56
views
tifr2016
matrices
complexnumber
+5
votes
2
answers
24
TIFR2016A5
For a positive integer $N \geq 2$, let $$A_N := \Sigma_{n=2}^N \frac{1}{n};$$ $$B_N := \int\limits_{x=1}^N \frac{1}{x} dx$$ Which of the following statements is true? As $N \rightarrow \infty, \: A_N$ increases to infinity but $B_N$ coverages to a ... < A_N +1$ $B_N < A_N < B_N +1$ As $N \rightarrow \infty, \: B_N$ increases to infinity but $A_N$ coverages to a finite number
asked
Dec 26, 2016
in
Others
by
jothee
Veteran
(
112k
points)

133
views
tifr2016
convergence
divergence
integration
+6
votes
2
answers
25
TIFR2016A4
There are $n$ balls $b_1, \dots ,b_n$ and $n$ boxes. Each ball is placed in box chosen independently and uniformly at random. We say that $(b_i, b_j)$ is a $\textit{colliding pair}$ if $i<j$, and $b_i$ and $b_j$ are placed in the same box. WHat is the expected number of $\textit{colliding pairs}$? $\frac{n1}{2}$ $0$ $1$ $\frac{n}{4}$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$
asked
Dec 26, 2016
in
Others
by
jothee
Veteran
(
112k
points)

215
views
tifr2016
probability
uniformhashing
+2
votes
0
answers
26
TIFR2016A3
Consider the following set of $3n$ linear equations in $3n$ variables: $\begin{matrix} x_1x_2=0 & x_4x_5 =0 & \dots & x_{3n2}x_{3n1}=0 \\ x_2x_3=0 & x_5x_6=0 & & x_{3n1}x_{3n}=0 \\ x_1x_3=0 & x_4x_6 =0 & ... is a subspace of $\mathbb{R}^{3n}$ of dimension n $S$ is a subspace of $\mathbb{R}^{3n}$ of dimension $n1$ $S$ has exactly $n$ elements
asked
Dec 26, 2016
in
Others
by
jothee
Veteran
(
112k
points)

43
views
tifr2016
+3
votes
4
answers
27
TIFR2016A2
Consider the graph shown below: The following experiment is performed using this graph. First, an edge $e =\{i,j\}$ of the graph is chosen uniformly at random from the set of 9 possibilities. Next, a common neighbour $k$ of $i$ and $j$ is chosen, again uniformly from the set of possibilities. (Note that the ... 3\}$? $\frac{1}{6}$ $\frac{1}{4}$ $\frac{1}{3}$ $\frac{2}{3}$ $\frac{5}{6}$
asked
Dec 26, 2016
in
Others
by
jothee
Veteran
(
112k
points)

125
views
tifr2016
graph
probability
+4
votes
2
answers
28
TIFR2016A1
Suppose the following statements about three persons in a room are true. Chandni, Sooraj and Tara are in a room. Nobody else is in the room. Chandni is looking at Sooraj. Sooraj is looking at Tara. Chandni is married. Tara is not ... is unmarried The situation described is impossible There is insufficient information to conclude if Sooraj is married or unmarried None of the above
asked
Dec 26, 2016
in
Numerical Ability
by
jothee
Veteran
(
112k
points)

150
views
tifr2016
logicalreasoning
+3
votes
1
answer
29
TIFR2016A12
There are two rocks $A$ and $B$, located close to each other, in a lily pond. There is a frog that jumps randomly between the two rocks at time $t = 0; 1; 2, \dots$. The location of the frog is determined as follows. Initially, at time $t = 0$, the frog is at $A$. From then on, the ... after its third jump)? $\frac{1}{2}$ $\frac{31}{54}$ $\frac{14}{27}$ $\frac{61}{108}$ $\frac{2}{3}$
asked
Oct 11, 2016
in
Probability
by
Ad Ri Ta
(
107
points)

140
views
tifr2016
probability
+18
votes
3
answers
30
TIFR2016B7
Let $n = m!$. Which of the following is TRUE? $m = \Theta (\log n / \log \log n)$ $m = \Omega (\log n / \log \log n)$ but not $m = O(\log n / \log \log n)$ $m = \Theta (\log^2 n)$ $m = \Omega (\log^2 n)$ but not $m = Ο( (\log^2 n)$ $m = \Theta (\log^{1.5} n)$
asked
Dec 13, 2015
in
Algorithms
by
Rohith AP
(
115
points)

779
views
tifr2016
asymptoticnotations
To see more, click for the
full list of questions
or
popular tags
.
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
My GATE journey
Believe..!!
Need a Serious Career Advice
Failure... ?
Applying to NUS
Follow @csegate
Gatecse
Recent questions tagged tifr2016
Recent Blog Comments
Congrats and Best of luck for life ahead :)
Congrats and Best of luck for life ahead :)
Congratulations @Hemant :) I am so happy for u. ...
Have u taken any online coaching ??
Same is for me. I am getting score 584. 2017 ...
34,239
questions
40,932
answers
116,230
comments
39,846
users