# Recent questions tagged tifr2016

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
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
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
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$
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
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
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 \}.$
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
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$
10
Consider the recursive function $\mathsf{mc91}$ ... $\{ n: 0 \leq n \leq 110 \}$ $\{ n: 0 \leq n \leq 111 \}$ $\{ n: 0 \leq n < + \infty \}$
11
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).$ ...
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
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
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)$
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$
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$
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$
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
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$
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
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
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$
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
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
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}$
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
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}$
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}$
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)$