search
Log In

Recent questions tagged tifr2016

2 votes
1 answer
1
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$ path. Let $a, b, c$ ... not 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 jothee 232 views
5 votes
1 answer
2
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 Venn ... $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n-1}$ None of the above
asked Dec 29, 2016 in Others jothee 285 views
2 votes
2 answers
3
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? $G$ ... $G$ There is a polynomial time algorithm to check if $G$ is 2-colourable If $G$ has no triangle then it is 3-colourable
asked Dec 29, 2016 in Others jothee 165 views
5 votes
1 answer
4
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 performed. x="01" ... $n < 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 jothee 172 views
5 votes
1 answer
5
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{R}^n\};$ ... ? $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 jothee 171 views
3 votes
1 answer
6
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$ ... $\mid C \mid \: \: \geq \: \: \mid V(G)\mid /2$ $C$ intersects every independent set
asked Dec 29, 2016 in Others jothee 160 views
5 votes
1 answer
7
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$ ... set $ E(G) = \{ \{i, j\} : 1 \leq i < j \leq 5 \: or \: 5 \leq i < j \leq 9 \}.$
asked Dec 29, 2016 in Others jothee 372 views
3 votes
1 answer
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 regular $\mathsf{PRIMES}$ is undecidable $\mathsf{PRIMES}$ is decidable in polynomial time $\mathsf{PRIMES}$ is context free but not regular $\mathsf{PRIMES}$ is NP-complete and P $\neq$ NP
asked Dec 29, 2016 in Others jothee 176 views
2 votes
0 answers
9
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 -\{x\}$ ... $x \in X$, then $\lambda x \in X$ for all scalars $\lambda$ If $x, y \in X$, then $x-y \in X$
asked Dec 28, 2016 in Others jothee 119 views
5 votes
1 answer
10
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 jothee 171 views
17 votes
2 answers
11
2 votes
1 answer
12
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
asked Dec 28, 2016 in Others jothee 132 views
2 votes
1 answer
13
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
asked Dec 28, 2016 in Others jothee 131 views
10 votes
5 answers
14
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 jothee 589 views
23 votes
5 answers
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 order of their total points ... 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 jothee 1.1k views
2 votes
3 answers
16
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 polygon with $n$ ... be determined from the information given $\frac{n}{2}-2$ $\frac{n}{4}-1$ $n-4$ $n^2 - 9.5 n +22$
asked Dec 28, 2016 in Others jothee 213 views
3 votes
3 answers
17
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 product of any $n$ ... $ i \in \{1, 2, \dots , n-1\}$ If $n$ is an odd prime, then $n$ divides $2^{n-1} -1$
asked Dec 28, 2016 in Others jothee 213 views
3 votes
1 answer
18
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 most 1.5 ... 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 jothee 191 views
2 votes
2 answers
19
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$ $s_{4k+1}$ ... is 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 jothee 128 views
2 votes
3 answers
20
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) is FALSE? $p$ ... 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 jothee 224 views
18 votes
4 answers
21
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 jothee 899 views
4 votes
1 answer
22
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 either move ... $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 jothee 184 views
2 votes
1 answer
23
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 The only eigen value ... 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 jothee 139 views
6 votes
2 answers
24
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
asked Dec 26, 2016 in Others jothee 304 views
8 votes
3 answers
25
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{n-1}{2}$ $0$ $1$ $\frac{n}{4}$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$
asked Dec 26, 2016 in Others jothee 491 views
2 votes
0 answers
26
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_{3n-1}-x_{3n}=0 \\ x_1-x_3=0 & x_4-x_6 =0 & & x_{3n-2}=x_{3n}=0 \end{matrix}$ ... $S$ is a subspace of $\mathbb{R}^{3n}$ of dimension n $S$ is a subspace of $\mathbb{R}^{3n}$ of dimension $n-1$ $S$ has exactly $n$ elements
asked Dec 26, 2016 in Others jothee 115 views
6 votes
4 answers
27
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 set ... $\frac{1}{6}$ $\frac{1}{4}$ $\frac{1}{3}$ $\frac{2}{3}$ $\frac{5}{6}$
asked Dec 26, 2016 in Others jothee 247 views
4 votes
2 answers
28
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 married. A ... Sooraj 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 jothee 360 views
4 votes
1 answer
29
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 on, the frog ... $\frac{1}{2}$ $\frac{31}{54}$ $\frac{14}{27}$ $\frac{61}{108}$ $\frac{2}{3}$
asked Oct 11, 2016 in Probability Ad Ri Ta 470 views
36 votes
6 answers
30
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 Rohith AP 2.6k views
To see more, click for the full list of questions or popular tags.
...