Dark Mode

Recent questions tagged tifr2016

2 votes

1 answer

1

doubt
https://gateoverflow.in/30720/tifr2016-b-7 the above question is already discussed but still am not clear enuf can someone help

A_i_$_h asked in Algorithms Oct 22, 2017

266 views

3 votes

1 answer

2

TIFR CSE 2016 | Part B | Question: 15
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 $x-y$ ... 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

go_editor asked in Graph Theory Dec 29, 2016

575 views

6 votes

1 answer

3

TIFR CSE 2016 | Part B | Question: 14
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? ... $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n-1}$ None of the above

go_editor asked in Set Theory & Algebra Dec 29, 2016

661 views

3 votes

4 answers

4

TIFR CSE 2016 | Part B | Question: 13
An undirected 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 ... degree in $G$ There is a polynomial time algorithm to check if $G$ is $2$-colourable If $G$ has no triangle then it is $3$-colourable

go_editor asked in Graph Theory Dec 29, 2016

698 views

6 votes

1 answer

5

TIFR CSE 2016 | Part B | Question: 12
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 ... $n^2 < t \leq n^{\log_2 n}$ $ n^{\log_2 n} < t \leq 2^{(2n)}$ $2^{(2n)} < t$

go_editor asked in Algorithms Dec 29, 2016

474 views

6 votes

1 answer

6

TIFR CSE 2016 | Part B | Question: 11
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$ ... inifinite number of vertices The diameter of $H$ is infinite $H$ is conneceted $H$ contains an infinite clique $H$ contains an infinite independent set

go_editor asked in Graph Theory Dec 29, 2016

501 views

4 votes

1 answer

7

TIFR CSE 2016 | Part B | Question: 10
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 ... $\mid C \mid \: \: \geq \: \: \mid V(G)\mid /2$ $C$ intersects every independent set

go_editor asked in Graph Theory Dec 29, 2016

546 views

6 votes

1 answer

8

TIFR CSE 2016 | Part B | Question: 9
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 ...

go_editor asked in Graph Theory Dec 29, 2016

1.6k views

5 votes

1 answer

9

TIFR CSE 2016 | Part B | Question: 8
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 decidable in polynomial time $\mathsf{PRIMES}$ is context free but not regular $\mathsf{PRIMES}$ is NP-complete and P $\neq$ NP

go_editor asked in Theory of Computation Dec 29, 2016

468 views

2 votes

0 answers

10

TIFR CSE 2016 | Part B | Question: 6
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 $x-y \in X$

go_editor asked in Linear Algebra Dec 28, 2016

330 views

6 votes

1 answer

11

TIFR CSE 2016 | Part B | Question: 5
Consider the recursive function $\mathsf{mc91}$ ... $\{ n: 0 \leq n \leq 110 \}$ $\{ n: 0 \leq n \leq 111 \}$ $\{ n: 0 \leq n < + \infty \}$

go_editor asked in Programming Dec 28, 2016

422 views

23 votes

4 answers

12

TIFR CSE 2016 | Part B | Question: 4
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 ...

go_editor asked in Mathematical Logic Dec 28, 2016

2.3k views

3 votes

1 answer

13

TIFR CSE 2016 | Part B | Question: 3
Assume $P \neq NP$. Which of the following is not TRUE? $2$-SAT in NP $2$-SAT in coNP $3$-SAT is polynmial-time reducible to $2$-SAT 4-SAT is polynmial-time reducible to $3$-SAT $2$-SAT in P

go_editor asked in Theory of Computation Dec 28, 2016

439 views

3 votes

1 answer

14

TIFR CSE 2016 | Part B | Question: 2
Which language class has the following properties? $\quad$ It is closed under union and intersection but not complement. Regular language Context-free language Recursive language Recursively enumerable language Languages that are not recursively enumerable

go_editor asked in Theory of Computation Dec 28, 2016

401 views

13 votes

5 answers

15

TIFR CSE 2016 | Part B | Question: 1
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)$

go_editor asked in Mathematical Logic Dec 28, 2016

1.6k views

32 votes

5 answers

16

TIFR CSE 2016 | Part A | Question: 15
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 ... of points a team must earn in order to be guaranteed a place in the next round? $13$ $12$ $11$ $10$ $9$

go_editor asked in Combinatory Dec 28, 2016

5.0k views

3 votes

3 answers

17

TIFR CSE 2016 | Part A | Question: 14
A $diagonal$ in a polygon is a straight line segment that connects two non-adjacent 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 ... the information given $\frac{n}{2}-2$ $\frac{n}{4}-1$ $n-4$ $n^2 - 9.5 n +22$

go_editor asked in Graph Theory Dec 28, 2016

583 views

4 votes

3 answers

18

TIFR CSE 2016 | Part A | Question: 13
Let $n \geq 2$ be any integer. Which of the following statements is not necessarily true? $\begin{pmatrix} n \\ i \end{pmatrix} = \begin{pmatrix} n-1 \\ i \end{pmatrix} + \begin{pmatrix} n-1 \\ i-1 \end{pmatrix}, \text{ where } 1 \leq i \leq n-1$ $n!$ divides the ... $ i \in \{1, 2, \dots , n-1\}$ If $n$ is an odd prime, then $n$ divides $2^{n-1} -1$

go_editor asked in Combinatory Dec 28, 2016

669 views

4 votes

1 answer

19

TIFR CSE 2016 | Part A | Question: 11
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 ... Which of the above statements is necessarily true? ii only iii only i, ii and iii ii and iii only None of the above

go_editor asked in Probability Dec 28, 2016

482 views

3 votes

2 answers

20

TIFR CSE 2016 | Part A | Question: 10
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_{n-1} +s_{n-2}+s_{n-3}$, for $n \geq 3$. Which of the following statements is FALSE? $s_{4k}$ is even, for any $ k \geq 0$ ... $ 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$

go_editor asked in Quantitative Aptitude Dec 27, 2016

346 views

3 votes

3 answers

21

TIFR CSE 2016 | Part A | Question: 9
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 ... values between $55$ and $60$ $p$ can be $70$ for some configuration $p$ can be $39$ for some configuration

go_editor asked in Quantitative Aptitude Dec 27, 2016

550 views

19 votes

4 answers

22

TIFR CSE 2016 | Part A | Question: 8
Let $A$ and $B$ be finite sets such that $A \subseteq B$. Then, what is the value of the expression: $ \sum \limits_{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 size of the universe

go_editor asked in Set Theory & Algebra Dec 27, 2016

1.9k views

5 votes

1 answer

23

TIFR CSE 2016 | Part A | Question: 7
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, from the point $(x, y)$ one ... 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$

go_editor asked in Combinatory Dec 27, 2016

467 views

3 votes

1 answer

24

TIFR CSE 2016 | Part A | Question: 6
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^{n-1}$, where $\omega$ is a primitive $n$-th root of unity ... there are no other eigen values The eigen values are $1, 1/2, 1/3, \dots , 1/n$ The only eigen value is $1$

go_editor asked in Linear Algebra Dec 26, 2016

417 views

7 votes

2 answers

25

TIFR CSE 2016 | Part A | Question: 5
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$ ... $B_N < A_N < B_N +1$ As $N \rightarrow \infty, \: B_N$ increases to infinity but $A_N$ coverages to a finite number

go_editor asked in Calculus Dec 26, 2016

693 views

9 votes

3 answers

26

TIFR CSE 2016 | Part A | Question: 4
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 ... $\frac{n-1}{2}$ $0$ $1$ $\frac{n}{4}$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$

go_editor asked in Probability Dec 26, 2016

1.3k views

3 votes

1 answer

27

TIFR CSE 2016 | Part A | Question: 3
Consider the following set of $3n$ linear equations in $3n$ ... $\mathbb{R}^{3n}$ of dimension n $S$ is a subspace of $\mathbb{R}^{3n}$ of dimension $n-1$ $S$ has exactly $n$ elements

go_editor asked in Linear Algebra Dec 26, 2016

375 views

7 votes

5 answers

28

TIFR CSE 2016 | Part A | Question: 2
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 ... $\frac{1}{6}$ $\frac{1}{4}$ $\frac{1}{3}$ $\frac{2}{3}$ $\frac{5}{6}$

go_editor asked in Graph Theory Dec 26, 2016

697 views

4 votes

2 answers

29

TIFR CSE 2016 | Part A | Question: 1
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. ... The situation described is impossible There is insufficient information to conclude if Sooraj is married or unmarried None of the above

go_editor asked in Analytical Aptitude Dec 26, 2016

885 views

6 votes

1 answer

30

TIFR CSE 2016 | Part A | Question: 12
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$ ... its third jump)? $\frac{1}{2}$ $\frac{31}{54}$ $\frac{14}{27}$ $\frac{61}{108}$ $\frac{2}{3}$

Ad Ri Ta asked in Probability Oct 11, 2016

914 views

Page:

Recent questions tagged tifr2016