Recent questions tagged tifr2016 / GATE Overflow for GATE CSE

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

https://gateoverflow.in/30720/tifr2016-b-7the above question is already discussedbut still am not clear enufcan someone help

A_i_$_h

427 views

A_i_$_h asked Oct 22, 2017

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

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$ s...

go_editor

827 views

go_editor asked Dec 29, 2016

7 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

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...

go_editor

1.0k views

go_editor asked Dec 29, 2016

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

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...

go_editor

1.2k views

go_editor asked Dec 29, 2016

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$

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$ a...

go_editor

730 views

go_editor asked Dec 29, 2016

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

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 \math...

go_editor

723 views

go_editor asked Dec 29, 2016

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

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 $...

go_editor

815 views

go_editor asked Dec 29, 2016

7 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 and returns to the vertex after traveling on each edge exactly once.) $K_{9, 9}$ $K_{8, 8}$ $K_{12, 12}$ $K_9$ The ...

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 an...

go_editor

2.2k views

go_editor asked Dec 29, 2016

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

Consider the following language$$\mathsf{PRIMES} = \Biggl\{ \underbrace{111 \dots 11}_{p \: \text{ times} } : \: p \: \text{ is prime } \Biggl\}$$Then, which of the follo...

go_editor

677 views

go_editor asked Dec 29, 2016

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$

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...

go_editor

464 views

go_editor asked Dec 28, 2016

7 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 \}$

Consider the recursive function $\mathsf{mc91}$.int mc91(int n) { print n if (n 100) { return n-10; } else { return mc91(mc91(n+11)); } }Let $\mathsf{Out}=\{n : \text{ t...

go_editor

653 views

go_editor asked Dec 28, 2016

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 ...

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 :...

go_editor

3.2k views

go_editor asked Dec 28, 2016

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

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$-SAT4-SAT is polynmial-time reducible to $3$-...

go_editor

643 views

go_editor asked Dec 28, 2016

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

Which language class has the following properties?$\quad$ It is closed under union and intersection but not complement.Regular languageContext-free languageRecursive lang...

go_editor

624 views

go_editor asked Dec 28, 2016

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)$

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) \w...

go_editor

2.2k views

go_editor asked Dec 28, 2016

34 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$

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...

go_editor

5.8k views

go_editor asked Dec 28, 2016

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$

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...

go_editor

876 views

go_editor asked Dec 28, 2016

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$

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} + ...

go_editor

1.1k views

go_editor asked Dec 28, 2016

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

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 ...

go_editor

678 views

go_editor asked Dec 28, 2016

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$

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 follo...

go_editor

527 views

go_editor asked Dec 27, 2016

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

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 lengt...

go_editor

818 views

go_editor asked Dec 27, 2016

20 votes

5 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

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...

go_editor

2.7k views

go_editor asked Dec 27, 2016

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$

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 ...

go_editor

781 views

go_editor asked Dec 27, 2016

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$

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, \omeg...

go_editor

586 views

go_editor asked Dec 26, 2016

8 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

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 \...

go_editor

1.1k views

go_editor asked Dec 26, 2016

10 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}$

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{colli...

go_editor

1.9k views

go_editor asked Dec 26, 2016

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

Consider the following set of $3n$ linear equations in $3n$ variables:$\begin{matrix} x_1-x_2=0 & x_4-x_5 =0 & \dots & x_{3n-2}-x_{3n-1}=0 \\ x_2-x_3=0 & x_5-x_6=0 & & x_...

go_editor

549 views

go_editor asked Dec 26, 2016

8 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}$

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...

go_editor

1.1k views

go_editor asked Dec 26, 2016

5 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

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. ...

go_editor

1.3k views

go_editor asked Dec 26, 2016

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}$

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 ...

Ad Ri Ta

1.2k views

Ad Ri Ta asked Oct 11, 2016

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