Register

Recent questions tagged tifr2012

1.1k
views
1 answers
7 votes
TIFR CSE 2012 | Part B | Question: 20
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 ... none of the above
User Avatar
3.0k
views
2 answers
24 votes
TIFR CSE 2012 | Part B | Question: 19
Which of the following statements is TRUE?Every turning machine recognizable language is recursive.The complement of every recursively enumerable language is recursively ... do not halt on empty input forms a recursively enumerable set.
User Avatar
1.6k
views
3 answers
13 votes
TIFR CSE 2012 | Part B | Question: 18
Let $a^{i}$ denote a sequence $a . a ... a$ with $i$ letters and let $\aleph$ be the set of natural numbers ${ 1, 2,...}$ ... free.$L_{1}$ is regular and $L_{2}$ is context-free.Complement of $L_{2}$ is context-free.
User Avatar
2.6k
views
2 answers
16 votes
TIFR CSE 2012 | Part B | Question: 17
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 ... with $k$ symbol to the right as look-ahead to give left-most derivation.
User Avatar
2.0k
views
1 answers
10 votes
TIFR CSE 2012 | Part B | Question: 16
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 ... .Linear in $n$.Logarithmic in $n$.Of the order square root of $n$.
User Avatar
4.0k
views
8 answers
29 votes
TIFR CSE 2012 | Part B | Question: 15
Let $T$ be a tree of $n$ nodes. Consider the following algorithm, that constructs a sequence of leaves $u_{1}, u_{2}...$. Let $u_{1}$ be some leaf of ... two vertices visited can be different, based on the choice of the first leaf $u_{1}$.
User Avatar
3.9k
views
3 answers
18 votes
TIFR CSE 2012 | Part B | Question: 14
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. ... time of the algorithm is $\Theta (n^{2})$.None of the above.
User Avatar
3.6k
views
4 answers
30 votes
TIFR CSE 2012 | Part B | Question: 13
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 ... .$A$ can be sorted with constant $\cdot k^{2}n$ comparisons but not fewer.
User Avatar
3.3k
views
2 answers
22 votes
TIFR CSE 2012 | Part B | Question: 12
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.
User Avatar
2.7k
views
3 answers
22 votes
TIFR CSE 2012 | Part B | Question: 11
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 ... correct.Both Program $2$ and $3$ are correctAll the three programs are wrong
User Avatar
3.8k
views
3 answers
27 votes
TIFR CSE 2012 | Part B | Question: 10
Consider the blocked-set semaphore where the signaling process awakens any one of the suspended process; i.e.,Wait (S): If $S>0$ ... $N\geq 1$
User Avatar
2.3k
views
1 answers
22 votes
TIFR CSE 2012 | Part B | Question: 9
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 ... $\left\{3, 5\right\}$
User Avatar
2.8k
views
2 answers
19 votes
TIFR CSE 2012 | Part B | Question: 8
Consider the parse treeAssume that $*$ has higher precedence than $+$, $-$ and operators associate right to left (i.e $(a + b + c= (a + (b + c)))$. ... (ii)Expression (iv) onlyExpression (ii), (iii), and (iv)Expression (iii) and (iv) only
User Avatar
2.2k
views
1 answers
15 votes
TIFR CSE 2012 | Part B | Question: 7
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 using a string ... $\dfrac{15}{8}\\$\dfrac{31}{16}\\$2$
User Avatar
4.5k
views
4 answers
25 votes
TIFR CSE 2012 | Part B | Question: 6
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}$ ... n}}<\frac{n}{\log n}$\frac{n}{\log n}< 2^\sqrt{{2\log n}}<n^{1/3}$
User Avatar
2.1k
views
3 answers
14 votes
TIFR CSE 2012 | Part B | Question: 5
Let $R$ be a binary relation over a set $S$. The binary relation $R$ is called an equivalence relation if it is reflexive transitive and symmetric. The ... a well order.$\sqsubseteq $ is neither a partial order nor an equivalence relation.
User Avatar
4.7k
views
4 answers
16 votes
TIFR CSE 2012 | Part B | Question: 4
Let $\wedge $, $\vee $ denote the meet and join operations of lattice. A lattice is called distributive if for all $x, y, z,$x\wedge \left ( ... but not a complete lattice.Under the give ordering positive integers do not form a lattice.
User Avatar
2.3k
views
5 answers
26 votes
TIFR CSE 2012 | Part B | Question: 3
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 ...
User Avatar
3.1k
views
3 answers
17 votes
TIFR CSE 2012 | Part B | Question: 2
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 ... .There are odd number of vertices of odd degree.All the vertices are of even degree.
User Avatar
2.3k
views
3 answers
17 votes
TIFR CSE 2012 | Part B | Question: 1
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$ ... $2^{2n}$2^{n+1}$2^{n-1}+1$n!$2^{n}$
User Avatar
3.1k
views
5 answers
23 votes
TIFR CSE 2012 | Part A | Question: 20
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 will ... 9/10$ but less than $1$.Less than $9/10$ but more than $0$.$0$1$
User Avatar
2.7k
views
2 answers
23 votes
TIFR CSE 2012 | Part A | Question: 19
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 are ... $\left(\dfrac{59}{60}\right)$
User Avatar
1.4k
views
1 answers
8 votes
TIFR CSE 2012 | Part A | Question: 18
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 the ratio of ... the babies are born male?$51:49$1:1$49:51$51:98$98:51$
User Avatar
2.5k
views
6 answers
10 votes
TIFR CSE 2012 | Part A | Question: 17
A spider is at the bottom of a cliff, and is $n$ inches from the top. Every step it takes brings it one inch closer to the top with probability $1/3$, and ... top.Linear in $n$.Polynomial in $n$.Exponential in $n$.Double exponential in $n$.
User Avatar
1.2k
views
2 answers
4 votes
TIFR CSE 2012 | Part A | Question: 16
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 data.
User Avatar
2.0k
views
2 answers
8 votes
TIFR CSE 2012 | Part A | Question: 15
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 above
User Avatar
1.9k
views
3 answers
7 votes
TIFR CSE 2012 | Part A | Question: 14
The limit $\displaystyle \lim_{n \rightarrow \infty} \left(\sqrt{n^{2}+n}-n\right)$ equals.$\infty$1$1 / 2$0$None of the above
User Avatar
1.5k
views
2 answers
3 votes
TIFR CSE 2012 | Part A | Question: 13
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}$ ... $1 / 3$2 / 3$1$4 / 3$4 / 9$
User Avatar
1.5k
views
2 answers
15 votes
TIFR CSE 2012 | Part A | Question: 12
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].$ ... .Only (i) and (iii).Only (ii) and (iii).All of (i), (ii) and (iii).
User Avatar
1.9k
views
3 answers
12 votes
TIFR CSE 2012 | Part A | Question: 11
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 ... significant byte (the least significant eight bits) of $N$?$00000000$10101110$01000000$10000000$11000000$
User Avatar
Page: