The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
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 ... iv i 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
(
105k
points)

201
views
tifr2016
+5
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 ... $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n1}$ None of the above
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
105k
points)

200
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 FALSE? ... 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
(
105k
points)

125
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 ... $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
(
105k
points)

146
views
tifr2016
+5
votes
1
answer
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$ ... $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
(
105k
points)

140
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 ... $\mid C \mid \: \: \geq \: \: \mid V(G)\mid /2$ $C$ intersects every independent set
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
105k
points)

132
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 ...
asked
Dec 29, 2016
in
Others
by
jothee
Veteran
(
105k
points)

298
views
tifr2016
discretemathematics
graphtheory
eulergraph
normal
+3
votes
0
answers
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}$ ... $\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
(
105k
points)

147
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$ ... $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
(
105k
points)

98
views
tifr2016
+5
votes
1
answer
10
TIFR2016B5
Consider the recursive function $\mathsf{mc91}$ ... $\{ 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
(
105k
points)

136
views
tifr2016
+16
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 ( ...
asked
Dec 28, 2016
in
Mathematical Logic
by
jothee
Veteran
(
105k
points)

939
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
(
105k
points)

105
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
(
105k
points)

110
views
tifr2016
theoryofcomputation
closureproperty
+9
votes
5
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 ( p \vee q)$
asked
Dec 28, 2016
in
Digital Logic
by
jothee
Veteran
(
105k
points)

395
views
tifr2016
booleanalgebra
+21
votes
5
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 their ... 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
(
105k
points)

809
views
tifr2016
permutationandcombination
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 polygon with ... 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
(
105k
points)

179
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 any ... $ 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
(
105k
points)

171
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 ... 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
(
105k
points)

155
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, for ... , 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
(
105k
points)

113
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$ ... $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
(
105k
points)

190
views
tifr2016
+15
votes
4
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
(
105k
points)

709
views
tifr2016
settheory&algebra
sets
+4
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 step ... $(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
(
105k
points)

153
views
tifr2016
permutationandcombination
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
(
105k
points)

117
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 finite ... $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
(
105k
points)

264
views
tifr2016
convergence
divergence
integration
+8
votes
3
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
(
105k
points)

414
views
tifr2016
probability
uniformhashing
+2
votes
0
answers
26
TIFR2016A3
Consider the following set of $3n$ linear equations in $3n$ ... 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
(
105k
points)

96
views
tifr2016
+5
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 ... $\frac{1}{6}$ $\frac{1}{4}$ $\frac{1}{3}$ $\frac{2}{3}$ $\frac{5}{6}$
asked
Dec 26, 2016
in
Others
by
jothee
Veteran
(
105k
points)

213
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
(
105k
points)

288
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, \ldots$. The location of the frog is determined as follows. Initially, at time $t = 0$, the frog is at $A$. From then ... (just 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
(
71
points)

370
views
tifr2016
probability
+32
votes
6
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
(
79
points)

2k
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged tifr2016
Recent Blog Comments
@CSHuB You need to choose "systems" as post...
@cshub.....if you are branch computer engineering...
Hey all! I can't see the CS branch here? How...
it's depends year to year
What was the average cutoff that was maintained...
50,741
questions
57,251
answers
198,057
comments
104,685
users