search
Log In

Recent questions tagged tifr2012

4 votes
1 answer
1
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 $L$ is in $P$ if there is some algorithm which given input $x$ decides if $x$ is in $L$ or not ... $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$ none of the above
asked Nov 15, 2015 in Algorithms Arjun 314 views
21 votes
2 answers
2
Which of the following statements is TRUE? Every turning machine recognizable language is recursive. The complement of every recursively enumerable language is recursively enumerable. The complement of a recursive language is recursively enumerable. The complement of a context-free ... is context-free. The set of turning machines which do not halt on empty input forms a recursively enumerable set.
asked Nov 2, 2015 in Theory of Computation makhdoom ghaya 975 views
11 votes
3 answers
3
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\right\}$ and $L_{2}=\left\{a^{i}b^{i^{2}}\mid i \in \aleph\right\}$ be ... free. Both $L_{1}$ and $L_{2}$ are recursive but not context-free. $L_{1}$ is regular and $L_{2}$ is context-free. Complement of $L_{2}$ is context-free.
asked Nov 2, 2015 in Theory of Computation makhdoom ghaya 563 views
13 votes
2 answers
4
Which of the following correctly describes $LR(k)$ parsing? The input string is alternately scanned left to right and right to left with $k$ reversals. Input string is scanned once left to right with rightmost derivation and $k$ symbol look-ahead. $LR(k)$ grammers ... string. Input string is scanned from left to right once with $k$ symbol to the right as look-ahead to give left-most derivation.
asked Nov 2, 2015 in Compiler Design makhdoom ghaya 702 views
8 votes
1 answer
5
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 effective resistance from the root to this bunch of leaves for very large $n$? Exponential in $n$. Cubic in $n$. Linear in $n$. Logarithmic in $n$. Of the order square root of $n$.
asked Nov 2, 2015 in DS makhdoom ghaya 570 views
21 votes
7 answers
6
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 tree. Let $u_{2}$be a leaf that is farthest from $u_{1}$. Let $u_{3}$ be the leaf that is ... then stays constant. For the same tree, the distance between the last two vertices visited can be different, based on the choice of the first leaf $u_{1}$.
asked Nov 2, 2015 in DS makhdoom ghaya 1.4k views
15 votes
4 answers
7
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. Then which of the following statements is TRUE? The running time of the algorithm is $\Theta (n).$ The running time ... algorithm is $\Theta (n^{1.5})$. The running time of the algorithm is $\Theta (n^{2})$. None of the above.
asked Nov 2, 2015 in Algorithms makhdoom ghaya 1.2k views
23 votes
3 answers
8
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 position in the sorted list. Assume that $n$ and $k$ are large and $k$ is much smaller ... with constant $.n \log k$ comparisons but not with fewer comparisons. $A$ can be sorted with constant $.k^{2}n$ comparisons but not fewer.
asked Nov 2, 2015 in Algorithms makhdoom ghaya 963 views
19 votes
2 answers
9
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.
asked Nov 1, 2015 in Linear Algebra makhdoom ghaya 1.1k views
18 votes
3 answers
10
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 sorted. i, j, k : integer; a : array [1....N] of T; x : T; Program 1 : i := 1; j := N ... correct Only Program $2$ is correct Only Program $1$ and $2$ are correct. Both Program $2$ and $3$ are correct All the three programs are wrong
asked Nov 1, 2015 in Algorithms makhdoom ghaya 789 views
22 votes
3 answers
11
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 the execution of this process. Signal (S): If there are processes that have been ... achieves mutual exclusion, but allows starvation for any $N\geq 2$ The program achieves mutual exclusion and starvation freedom for any $N\geq 1$
asked Oct 31, 2015 in Operating System makhdoom ghaya 1.2k views
17 votes
1 answer
12
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 atomic. The set of possible values of variable $x$ at the end of execution of the program is $\left\{3\right\}$ $\left\{7\right\}$ $\left\{3, 5, 7\right\}$ $\left\{3, 7\right\}$ $\left\{3, 5\right\}$
asked Oct 31, 2015 in Operating System makhdoom ghaya 883 views
16 votes
2 answers
13
Consider the parse tree Assume 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 - b * a + b$ $2 + ((a - b) * (a + b)))$ $2 + (a - b) * (a + b)$ The parse tree corresponds to Expression (i) Expression (ii) Expression (iv) only Expression (ii), (iii), and (iv) Expression (iii) and (iv) only
asked Oct 31, 2015 in Compiler Design makhdoom ghaya 865 views
11 votes
1 answer
14
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 of zeros and ones. She replaces the ball in the bag, and repeats this experiment, many times. What is the minimum ... to Babu per experiment? $\dfrac{3}{2}\\$ ${\log 5}\\$ $\dfrac{15}{8}\\$ $\dfrac{31}{16}\\$ $2$
asked Oct 31, 2015 in Probability makhdoom ghaya 834 views
18 votes
3 answers
15
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\sqrt{^{2\log n}}< n^{1/3}< \frac{n}{\log n}$ $n^{1/3}< 2\sqrt{^{2\log n}}<\frac{n}{\log n}$ $\frac{n}{\log n}< 2\sqrt{^{2\log n}}<n^{1/3}$
asked Oct 31, 2015 in Algorithms makhdoom ghaya 1.2k views
10 votes
3 answers
16
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 relation is called partial order if it is reflexive, transitive and anti symmetric. (Notation: Let $aRb$ ... order. $\sqsubseteq $ is an equivalence relation and a well order. $\sqsubseteq $ is neither a partial order nor an equivalence relation.
asked Oct 31, 2015 in Set Theory & Algebra makhdoom ghaya 626 views
14 votes
4 answers
17
Let $\wedge $, $\vee $ denote the meet and join operations of lattice. A lattice is called distributive if for all $x, y, z,$ ... lattice. Modular, but not distributive lattice. Distributive lattice. Lattice but not a complete lattice. Under the give ordering positive integers do not form a lattice.
asked Oct 31, 2015 in Set Theory & Algebra makhdoom ghaya 1.6k views
21 votes
5 answers
18
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 following is the correct translation in first order logic of the sentence: "All woman who ...
asked Oct 30, 2015 in Mathematical Logic makhdoom ghaya 886 views
13 votes
2 answers
19
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 of even degree. There are odd number of vertices of even degree. There are even number of vertices of odd degree. There are odd number of vertices of odd degree. All the vertices are of even degree.
asked Oct 30, 2015 in Graph Theory makhdoom ghaya 686 views
14 votes
3 answers
20
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 function $F:\left\{0, 1\right\}^{n}\rightarrow\left\{0, 1\right\}$ is said to be linear if $F(x ⊕ y)= F(x) ⊕ F(y)$, ... functions from $\left\{0, 1\right\}^{n}$ to $\left\{0, 1\right\}$ is. $2^{2n}$ $2^{n+1}$ $2^{n-1}+1$ $n!$ $2^{n}$
asked Oct 30, 2015 in Set Theory & Algebra makhdoom ghaya 858 views
14 votes
4 answers
21
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 be black? $9/10$ More than $9/10$ but less than $1$. Less than $9/10$ but more than $0$. $0$ $1$
asked Oct 30, 2015 in Probability makhdoom ghaya 908 views
19 votes
2 answers
22
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 all independent. What is the probability that $A$ and $B$ are connected? $\left(\dfrac{6}{25}\right)$ ... $\left(\dfrac{1}{1200}\right)$ $\left(\dfrac{1199}{1200}\right)$ $\left(\dfrac{59}{60}\right)$
asked Oct 30, 2015 in Probability makhdoom ghaya 974 views
3 votes
1 answer
23
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 boys to girls in the community if, in the absence of birth control, 51% of the babies are born male? $51:49$ $1:1$ $49:51$ $51:98$ $98:51$
asked Oct 30, 2015 in Numerical Ability makhdoom ghaya 381 views
6 votes
5 answers
24
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 one inch away from the top with probability $2/3$, unless it is at the bottom in which case, it always gets one ... a function of $n$? It will never reach the top. Linear in $n$. Polynomial in $n$. Exponential in $n$. Double exponential in $n$.
asked Oct 30, 2015 in Probability makhdoom ghaya 836 views
3 votes
2 answers
25
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.
asked Oct 30, 2015 in Numerical Ability makhdoom ghaya 300 views
7 votes
2 answers
26
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.
asked Oct 30, 2015 in Calculus makhdoom ghaya 562 views
7 votes
3 answers
27
The limit $\lim_{n \rightarrow \infty} \left(\sqrt{n^{2}+n}-n\right)$ equals. $\infty$ $1$ $1 / 2$ $0$ None of the above.
asked Oct 30, 2015 in Calculus makhdoom ghaya 573 views
3 votes
2 answers
28
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 + y + z=1, x \geq 0, y \geq 0, z \geq 0$ is $1 / 3$ $2 / 3$ $1$ $4 / 3$ $4 / 9$
asked Oct 30, 2015 in Calculus makhdoom ghaya 435 views
10 votes
2 answers
29
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].$ It has no roots outside $(-1, 1).$ Which of the above statements are true? Only (i). Only (i) and (ii). Only (i) and (iii). Only (ii) and (iii). All of (i), (ii) and (iii).
asked Oct 30, 2015 in Set Theory & Algebra makhdoom ghaya 583 views
7 votes
1 answer
30
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). What is the value of the least significant byte (the least significant eight bits) of $N$? $00000000$ $10101110$ $01000000$ $10000000$ $11000000$
asked Oct 30, 2015 in Numerical Ability makhdoom ghaya 469 views
...