# Recent questions tagged tifr2013

1
Suppose $n$ processors are connected in a linear array as shown below. Each processor has a number. The processors need to exchange numbers so that the numbers eventually appear in ascending order (the processor $\rm P1$ should have the minimum value and the the processor $\rm Pn$ should ... values? $n \log n$ steps $n^2$ steps $n$ steps $n^{1.5}$ steps The algorithm is not guaranteed to sort
2
In a relational database there are three relations: Customers = $C$(CName), Shops = $S$(SName), Buys = $B$(CName, SName). Which of the following relational algebra expressions returns the names of shops that have no customers at all? [Here $\Pi$ is the projection operator.] $\Pi _{S Name}B$ $S - B$ $S - \Pi _{S Name}B$ $S - \Pi _{S Name}((C \times S) - B)$ None of the above
3
Let $S$ be a set of numbers. For $x \in S$, the rank of $x$ is the number of elements in $S$ that are less than or equal to $x$. The procedure Select$(S, r)$ takes a set $S$ of numbers and a rank $r\left(1 \leq r \leq |S|\right)$ and returns the element in $S$ of rank $r$. The ... · $|S| \log |S|$ constant · $|S|$ constant · $|S||R|$ constant · $|R| \log |S|$ constant · $|S|(1 + \log |R|)$
4
In a connected weighted graph with $n$ vertices, all the edges have distinct positive integer weights. Then, the maximum number of minimum weight spanning trees in the graph is $1$ $n$ equal to number of edges in the graph. equal to maximum weight of an edge of the graph. $n^{n-2}$
5
Consider a function $T_{k, n}: \left\{0, 1\right\}^{n}\rightarrow \left\{0, 1\right\}$ which returns $1$ if at least $k$ of its $n$ inputs are $1$. Formally, $T_{k, n}(x)=1$ if $\sum ^{n}_{1} x_{i}\geq k$. Let $y \in \left\{0, 1\right\}^{n}$ be such that $y$ has ... $y_{i}$ is omitted) is equivalent to $T_{k-1}, n(y)$ $T_{k, n}(y)$ $y_{i}$ $\neg y_{i}$ None of the above
6
Let $G$ be an undirected graph with $n$ vertices. For any subset $S$ of vertices, the set of neighbours of $S$ consists of the union of $S$ and the set of vertices $S'$ that are connected to some vertex in $S$ by an edge of $G$. The graph $G$ has the nice property that every subset of ... $O \left(\sqrt{n}\right)$ but not $O (\log n)$ $O (n)$ but not $O \left(\sqrt{n}\right)$
7
Assume a demand paged memory system where ONLY THREE pages can reside in the memory at a time. The following sequence gives the order in which the program references the pages. $1, 3, 1, 3, 4, 2, 2, 4$ Assume that least frequently used page is replaced when necessary. If ... , respectively $1,1,1,2$ times, respectively $1,1,1,1$ times, respectively $2,1,2,2$ times, respectively None of the above
8
Given a binary tree of the following form and having $n$ nodes, the height of the tree is $\Theta \left(\log n\right)$ $\Theta \left(n\right)$ $\Theta \left(\sqrt{n}\right)$ $\Theta \left(n / \log n\right)$ None of the above.
9
It takes $O(n)$ time to find the median in a list of $n$ elements, which are not necessarily in sorted order while it takes only $O(1)$ time to find the median in a list of $n$ sorted elements. How much time does it take to find the median of $2n$ elements which are given as two lists of $n$ ... not $O \left(\log n\right)$ $O (n)$ but not $O (\sqrt{n})$ $O \left(n \log n\right)$ but not $O (n)$
10
Which of the following statements is FALSE? The intersection of a context free language with a regular language is context free. The intersection of two regular languages is regular. The intersection of two context free languages is context free The intersection of a ... a regular language is context free. The intersection of a regular language and the complement of a regular language is regular.
11
Let $m, n$ be positive integers with $m$ a power of $2$. Let $s= 100 n^{2} \log m$. Suppose $S_{1}, S_{2},\dots ,S_{m}$ are subsets of ${1, 2, \dots, s}$ such that $\mid S_{i} \mid= 10 n \log m$ and $\mid S_{i} \cap S_{j} \mid \leq \log m$ for all $1 \leq i \lt j \leq m$. Such a ... $0.9$ if $x ∉ T$. $1$ if $x \in T$ and at least $0.9$ if $x ∉ T$. At least $0.9$ if $x \in T$ and $1$ if $x ∉ T$.
12
Suppose $n$ straight lines are drawn on a plane. When these lines are removed, the plane falls apart into several connected components called regions. $A$ region $R$ is said to be convex if it has the following property: whenever two points are in $R$, then the ... regions are produced, but they need not all be convex. All regions are convex but there may be exponentially many of them.
13
Which one of the following languages over the alphabet ${0, 1}$ is regular? The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively. The language of palindromes, i.e. bit strings $x$ ... $L^*$, where $L$ is the language in $(c)$ above. $\left \{ 0^{m} 1^{n} | 1 \leq m \leq n\right \}$
14
Which of the following is not implied by $P=NP$? $3$SAT can be solved in polynomial time. Halting problem can be solved in polynomial time. Factoring can be solved in polynomial time. Graph isomorphism can be solved in polynomial time. Travelling salesman problem can be solved in polynomial time.
15
Let $L$ and $L'$ be languages over the alphabet $\Sigma$. The left quotient of $L$ by $L'$ is $L/L'\overset{{def}}{=} \left\{w \in \Sigma^* : wx ∈ L\text{ for some }x \in L'\right\}$ Which of the following is true? If $L/L'$ is regular then $L'$ is regular. If $L$ is ... . If $L/L'$ is regular then $L$ is regular. $L/L'$ is a subset of $L$. If $L/L'$ and $L'$ are regular, then $L$ is regular.
16
Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large weight can be performed in time $O(n)$ $O(n . \log(n))$ but not $O (n)$ $O(n^{1.5})$ but not $O (n \log n)$ $O(n^{3})$ but not $O(n^{1.5})$ $O(2^{n})$ but not $O(n^{3})$
17
A set $S$ together with partial order $\ll$ is called a well order if it has no infinite descending chains, i.e. there is no infinite sequence $x_1, x_2,\ldots$ of elements from $S$ such that $x_{i+1} \ll x_i$ and $x_{i+1} \neq x_i$ for all $i$. Consider the set of all ... there are only $2^{24}$ words. $W$ is not a partial order. $W$ is a partial order but not a well order. $W$ is a well order.
18
How many $4 \times 4$ matrices with entries from ${0, 1}$ have odd determinant? Hint: Use modulo $2$ arithmetic. $20160$ $32767$ $49152$ $57343$ $65520$
19
Consider polynomials in a single variable $x$ of degree $d$. Suppose $d < n/2$. For such a polynomial $p(x)$, let $C_{p}$ denote the $n$-tuple $(P\left ( i \right ))_{1 \leq i \leq n}$. For any two such distinct polynomials $p, q,$ the number of coordinates where the tuples $C_{p}, C_{q}$ differ is. At most $d$ At most $n - d$ Between $d$ and $n - d$ At least $n - d$ None of the above.
20
Let $G= (V, E)$ be a simple undirected graph on $n$ vertices. A colouring of $G$ is an assignment of colours to each vertex such that endpoints of every edge are given different colours. Let $\chi (G)$ denote the chromatic number of $G$, i.e. the minimum numbers of colours needed for ... $a\left(G\right)\leq \frac{n}{\chi \left(G\right)}$ None of the above
21
Consider a well functioning clock where the hour, minute and the seconds needles are exactly at zero. How much time later will the minutes needle be exactly one minute ahead ($1/60$ th of the circumference) of the hours needle and the seconds needle again exactly at zero? ... an integer multiple of $1/60$ th of the circumference. $144$ minutes $66$ minutes $96$ minutes $72$ minutes $132$ minutes
22
Consider a sequence of numbers $\large (\epsilon _{n}: n= 1, 2,...)$, such that $\epsilon _{1}=10$ and $\large \epsilon _{n+1}=\dfrac{20\epsilon _{n}}{20+\epsilon _{n}}$ for $n\geq 1$. Which of the following statements is true? Hint: Consider the sequence of ... $\large (\epsilon _{n}: n= 1, 2,...)$ is decreasing and then increasing. Finally it converges to $1.$ None of the above.
23
Consider three independent uniformly distributed (taking values between $0$ and $1$) random variables. What is the probability that the middle of the three values (between the lowest and the highest value) lies between $a$ and $b$ where $0 ≤ a < b ≤ 1$? $3 (1 - b) a (b - a)$ $3 ((b - a) - (b^{2}- a^{2})/2)$ $6 (1 - b) a (b - a)$ $(1 - b) a (b - a)$ $6 ((b^{2}- a^{2})/ 2 - (b^{3} - a^{3})/3)$.
24
A stick of unit length is broken into two at a point chosen at random. Then, the larger part of the stick is further divided into two parts in the ratio $4:3$. What is the probability that the three sticks that are left CANNOT form a triangle? $1/4$ $1/3$ $5/6$ $1/2$ $\log_{e}(2)/2$
25
The minimum of the function $f(x) = x \log_{e}(x)$ over the interval $[\frac{1}{2}, \infty )$ is $0$ $-e$ $\frac{-\log_{e}(2)}{2}$ $\frac{-1}{e}$ None of the above
26
Let $\DeclareMathOperator{S}{sgn} \S (x)= \begin{cases} +1 & \text{if } x \geq 0 \\ -1 & \text{if } x < 0 \end{cases}$ What is the value of the following summation? $\sum_{i=0}^{50} \S \left ( (2i - 1) (2i - 3) \dots (2i - 99) \right)$ $0$ $-1$ $+1$ $25$ $50$
27
An unbiased die is thrown $n$ times. The probability that the product of numbers would be even is $\dfrac{1}{(2n)}$ $\dfrac{1}{[(6n)!]}$ $1 - 6^{-n}$ $6^{-n}$ None of the above
28
Doctors $A$ and $B$ perform surgery on patients in stages $III$ and $IV$ of a disease. Doctor $A$ has performed a $100$ surgeries (on $80$ stage $III$ and $20$ stage $IV$ patients) and $80$ out of her $100$ patients have survived ($78$ ... $B$ since she appears to be more successful There is not enough data since the choice depends on the stage of the disease the patient is suffering from.
29
Among numbers $1$ to $1000$ how many are divisible by $3$ or $7$? $333$ $142$ $475$ $428$ None of the above
Let there be a pack of $100$ cards numbered $1$ to $100$. The $i^{th}$ card states: "There are at most $i - 1$ true cards in this pack". Then how many cards of the pack contain TRUE statements? $0$ $1$ $100$ $50$ None of the above