Recent questions tagged tifr2012

This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question.Let $L$ be a set. We say that...

Which of the following statements is TRUE?Every turing machine recognizable language is recursive.The complement of every recursively enumerable language is recursively e...

Let $a^{i}$ denote a sequence $a . a ... a$ with $i$ letters and let $\aleph$ be the set of natural numbers ${ 1, 2,...}$. Let $L_{1}=\left\{a^{i}b^{2i}\mid i \in \aleph...

Which of the following correctly describes $\text{LR}(k)$ parsing?The input string is alternately scanned left to right and right to left with $k$ reversals.Input string ...

Consider a complete binary tree of height $n$, where each edge is one Ohm resistor. Suppose all the leaves of the tree are tied together. Approximately how much is the ef...

Consider the quick sort algorithm on a set of $n$ numbers, where in every recursive subroutine of the algorithm, the algorithm chooses the median of that set as the pivot...

An array $A$ contains $n$ integers. We wish to sort $A$ in ascending order. We are told that initially no element of $A$ is more than a distance $k$ away from its final p...

Let $A$ be a matrix such that $A^{k}=0$. What is the inverse of $I - A$?$0$$I$$A$$1 + A + A^{2} + ...+ A^{k - 1}$Inverse is not guaranteed to exist.

Consider the following three version of the binary search program. Assume that the elements of type $T$ can be compared with each other; also assume that the array is sor...

Consider the blocked-set semaphore where the signaling process awakens any one of the suspended process; i.e.,Wait (S): If $S>0$ then $S\leftarrow S - 1$, else suspend th...

Consider the concurrent program x := 1; cobegin x := x + x + 1 || x := x + 2 coend;Reading and writing of a variable is atomic, but evaluation of an expression is not a...

Consider the parse treeAssume that $*$ has higher precedence than $+$, $-$ and operators associate right to left (i.e $(a + b + c= (a + (b + c)))$. Consider$2 + a - b$$2 ...

A bag contains $16$ balls of the following colors: 8 red, 4 blue, 2 green, 1 black, and 1 white. Anisha picks a ball randomly from the bag, and messages Babu its color us...

Let $n$ be a large integer. Which of the following statements is TRUE?$2^{\sqrt{2\log n}}< \frac{n}{\log n}< n^{1/3}$$\frac{n}{\log n}< n^{1/3}< 2^{\sqrt{2\log n}}$$2^{\s...

For a person $p$, let $w(p)$, $A(p, y)$, $L(p)$ and $J(p)$ denote that $p$ is a woman, $p$ admires $y$, $p$ is a lawyer and $p$ is a judge respectively. Which of the foll...

In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph $G$?There are even number of vertices...

For $x, y\in \left\{0, 1\right\}^{n}$, let $x ⊕ y$ be the element of $\left\{0, 1\right\}^{n}$ obtained by the component-wise exclusive-or of $x$ and $y$. A Boolean funct...

There are $1000$ balls in a bag, of which $900$ are black and $100$ are white. I randomly draw $100$ balls from the bag. What is the probability that the $101$st ball wil...

An electric circuit between two terminals $A$ and $B$ is shown in the figure below, where the numbers indicate the probabilities of failure for the various links, which a...

A large community practices birth control in the following peculiar fashion. Each set of parents continues having children until a son is born; then they stop. What is th...

Walking at $4/5$ is normal speed a man is $10$ minute too late. Find his usual time in minutes.$81$$64$$52$$40$It is not possible to determine the usual time from given d...

Consider the differential equation $dx/dt= \left(1 - x\right)\left(2 - x\right)\left(3 - x\right)$. Which of its equilibria is unstable?$x=0$$x=1$$x=2$$x=3$None of the ab...

The limit $\displaystyle \lim_{n \rightarrow \infty} \left(\sqrt{n^{2}+n}-n\right)$ equals.$\infty$$1$$1 / 2$$0$None of the above

The maximum value of the function$f\left(x, y, z\right)= \left(x - 1 / 3\right)^{2}+ \left(y - 1 / 3\right)^{2}+ \left(z - 1 / 3\right)^{2}$subject to the constraints$x +...

For the polynomial $p(x)= 8x^{10}-7x^{3}+x-1$ consider the following statements (which may be true or false)It has a root between $[0, 1].$It has a root between $[0, -1]....

Let $N$ be the sum of all numbers from $1$ to $1023$ except the five primes numbers: $2, 3, 11, 17, 31.$ Suppose all numbers are represented using two bytes (sixteen bits...