search
Log In

Recent questions tagged tifr2015

19 votes
5 answers
1
Consider the following grammar (the start symbol is $E$) for generating expressions. $E \rightarrow T - E \mid T + E \mid T$ $T \rightarrow T * F \mid F$ $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$ With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?
asked Dec 8, 2015 in Compiler Design makhdoom ghaya 939 views
10 votes
3 answers
2
Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently). x:=1 cobegin x:= x + 1 || x:= x + 1 || x:= x + 1 coend Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values of $x$ ... $\left \{2, 4 \right \}$ $\left \{ 2, 3 \right \}$ $\left \{2 \right \}$
asked Dec 8, 2015 in Operating System makhdoom ghaya 792 views
4 votes
2 answers
3
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ if and only $( \pi (u), \pi (v)) \in E_{2}$. Consider the ... (ii) $L$ is $NP$- hard. (iii) $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$
asked Dec 8, 2015 in Algorithms makhdoom ghaya 270 views
8 votes
2 answers
4
Let $t_{n}$ be the sum of the first $n$ natural numbers, for $n > 0$. A number is called triangular if it is equal to $t_{n}$ for some $n$. Which of the following statements are true: (i) There exists three successive triangular numbers whose product is a perfect square. (ii) If the triangular ... $(i)$ only. $(ii)$ only. $(iii)$ only. All of the above. None of the above.
asked Dec 8, 2015 in Numerical Ability makhdoom ghaya 567 views
16 votes
2 answers
5
Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n}$? $\frac{m}{n - 1}$ $m^{n - 1}$ $n^{n - 2}$ $n^{n - 1}$ None of the above.
asked Dec 8, 2015 in Graph Theory makhdoom ghaya 818 views
18 votes
2 answers
6
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which of the following is true? $L_{1}$ ... $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.
asked Dec 8, 2015 in Theory of Computation makhdoom ghaya 834 views
22 votes
2 answers
7
A Boolean expression is an expression made out of propositional letters (such as $p, q, r$) and operators $\wedge$, $\vee$ and $\neg$; e.g. $p\wedge \neg (q \vee \neg r)$. An expression is said to be in sum of product form ... operator. Every Boolean expression is equivalent to an expression without $\wedge$ operator. Every Boolean expression is equivalent to an expression without $\neg$ operator.
asked Dec 8, 2015 in Digital Logic makhdoom ghaya 826 views
22 votes
5 answers
8
Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite length words comprising letters of the alphabet. Let $L_{1}$ and $L_{2}$ be the set of languages ... countably infinite. $L_{1}$ is countable but $L_{2}$ is not. $L_{2}$ is countable but $L_{1}$ is not. Neither of them is countable.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 1.4k views
17 votes
4 answers
9
Let $a, b, c$ be regular expressions. Which of the following identities is correct? $(a + b)^{*} = a^{*}b^{*}$ $a(b + c) = ab + c$ $(a + b)^{*} = a^{*} + b^{*}$ $(ab + a)^{*}a = a(ba + a)^{*}$ None of the above.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 748 views
12 votes
3 answers
10
Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$. $B$ can be recognized by a deterministic finite state automaton. $B$ can be recognized by a non-deterministic finite state automaton ... but not by a deterministic push-down automaton. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 735 views
22 votes
7 answers
11
Suppose $\begin{pmatrix} 0&1 &0&0&0&1 \\ 1&0&1&0&0&0 \\ 0&1&0&1&0&1 \\ 0&0&1&0&1&0 \\ 0&0&0&1&0&1 \\ 1&0&1&0&1&0 \end{pmatrix}$ is the adjacency matrix of an undirected graph with six vertices: that is, the rows and columns are indexed by vertices of the graph, and an entry is $1$ if the ... has the above adjacency matrix? Only $(i)$ Only $(ii)$ Only $(iii)$ Only $(iv)$ $(i)$ and $(ii)$
asked Dec 7, 2015 in Graph Theory makhdoom ghaya 1.1k views
32 votes
3 answers
12
First, consider the tree on the left. On the right, the nine nodes of the tree have been assigned numbers from the set $\left\{1, 2,\ldots,9\right\}$ so that for every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree are less than all numbers in ... $2^{4}.3^{2}.5.9=6480$ $2^{3}.3.5.9=1080$ $2^{4}=16$ $2^{3}.3^{3}=216$
asked Dec 7, 2015 in DS makhdoom ghaya 1.6k views
16 votes
2 answers
13
Consider the following code fragment in the $C$ programming language when run on a non-negative integer $n$. int f (int n) { if (n==0 || n==1) return 1; else return f (n - 1) + f(n - 2); } Assuming a typical implementation of the language, what ... polynomial in $n$. This algorithm runs in polynomial time in $n$ and the optimal running time is polynomial in $n$. The algorithm does not terminate.
asked Dec 7, 2015 in Algorithms makhdoom ghaya 602 views
25 votes
2 answers
14
Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum spanning ... minimum spanning tree here. There is unique minimum spanning tree, however there is more than one second-best minimum spanning tree here.
asked Dec 7, 2015 in Algorithms makhdoom ghaya 1.1k views
21 votes
2 answers
15
Consider the following recurrence relation: $T(n) = \begin{cases} 2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$ Which of the following statements is TRUE? $T(n)$ is $O(\log n)$. $T(n)$ is $O(\log n. \log \log n)$ but not $O(\log n)$. $T(n)$ is ... $O(\log^{2} n)$ but not $O(\log^{3/2} n)$. $T(n)$ is $O(\log^{2} n. \log \log n)$ but not $O(\log^{2} n)$.
asked Dec 5, 2015 in Algorithms makhdoom ghaya 921 views
5 votes
2 answers
16
Let $A$ and $B$ be non-empty disjoint sets of real numbers. Suppose that the average of the numbers in the first set is $\mu_{A}$ and the average of the numbers in the second set is $\mu_{B}$; let the corresponding variances be $v_{A}$ and $v_{B}$ respectively. If the average of the elements in $A \cup B$ ... $p.v_{A}+ (1 - p). v_{B} + (\mu_{A}- \mu_{B})^{2}$
asked Dec 5, 2015 in Numerical Ability makhdoom ghaya 340 views
10 votes
1 answer
17
Consider the following $3 \times 3$ matrices. $M_{1}=\begin{pmatrix} 0&1&1 \\ 1&0&1 \\ 1&1&0 \end{pmatrix} $ $M_{2}=\begin{pmatrix} 1&0&1 \\ 0&0&0 \\ 1&0&1 \end{pmatrix} $ How may $0-1$ column vectors of the form $X$ ... $2$ means all operations are done modulo $2$, i.e, $3 = 1$ (modulo $2$), $4 = 0$ (modulo $2$)). None Two Three Four Eight
asked Dec 5, 2015 in Linear Algebra makhdoom ghaya 617 views
9 votes
2 answers
18
Imagine the first quadrant of the real plane as consisting of unit squares. A typical square has $4$ corners: $(i, j), (i+1, j), (i+1, j+1),$and $(i, j+1)$, where $(i, j)$ is a pair of non-negative integers. Suppose a line segment $l$ connecting $(0, 0)$ to ... through a point in the interior of the square. How many unit squares does $l$ pass through? $98,990$ $9,900$ $1,190$ $1,180$ $1,010$
asked Dec 5, 2015 in Numerical Ability makhdoom ghaya 797 views
4 votes
2 answers
19
Consider two independent and identically distributed random variables $X$ and $Y$ uniformly distributed in $[0, 1]$. For $\alpha \in \left[0, 1\right]$, the probability that $\alpha$ max $(X, Y) < XY$ is $1/ (2\alpha)$ exp $(1 - \alpha)$ $1 - \alpha$ $(1 - \alpha)^{2}$ $1 - \alpha^{2}$
asked Dec 5, 2015 in Probability makhdoom ghaya 389 views
11 votes
5 answers
20
Suppose that $f(x)$ is a continuous function such that $0.4 \leq f(x) \leq 0.6$ for $0 \leq x \leq 1$. Which of the following is always true? $f(0.5) = 0.5$. There exists $x$ between $0$ and $1$ such that $f(x) = 0.8x$. There exists $x$ between $0$ and $0.5$ such that $f(x) = x$. $f(0.5) > 0.5$. None of the above statements are always true.
asked Dec 5, 2015 in Calculus makhdoom ghaya 813 views
4 votes
0 answers
21
Let $f(x), x\in \left[0, 1\right]$, be any positive real valued continuous function. Then $\displaystyle \lim_{n \rightarrow \infty} (n + 1) \int_{0}^{1} x^{n} f(x) \text{d}x$ equals. $\max_{x \in \left[0, 1\right]} f(x)$ $\min_{x \in \left[0, 1\right]} f(x)$ $f(0)$ $f(1)$ $\infty$
asked Dec 5, 2015 in Calculus makhdoom ghaya 243 views
3 votes
2 answers
22
Consider a square of side length $2$. We throw five points into the square. Consider the following statements: There will always be three points that lie on a straight line. There will always be a line connecting a pair of points such that two points lie on one side of the line and one point on the ... the above is true: $(i)$ only. $(ii)$ only. $(iii)$ only. $(ii)$ and $(iii)$. None of the above.
asked Dec 5, 2015 in Numerical Ability makhdoom ghaya 344 views
23 votes
3 answers
23
There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is. $2^{n}$ $n^{2}$ $\binom{n}{⌊n/2⌋}^{2}$ $\binom{2n}{n}$ None of the above.
asked Dec 5, 2015 in Combinatory makhdoom ghaya 1.4k views
15 votes
7 answers
24
A $1 \times 1$ chessboard has one square, a $2 \times 2$ chessboard has five squares. Continuing along this fashion, what is the number of squares on the regular $8 \times 8$ chessboard? $64$ $65$ $204$ $144$ $256$
asked Dec 5, 2015 in Combinatory makhdoom ghaya 1k views
11 votes
5 answers
25
Ram has a fair coin, i.e., a toss of the coin results in either head or tail and each event happens with probability exactly half $(1/2)$. He repeatedly tosses the coin until he gets heads in two consecutive tosses. The expected number of coin tosses that Ram does is. $2$ $4$ $6$ $8$ None of the above.
asked Dec 5, 2015 in Probability makhdoom ghaya 1.7k views
14 votes
3 answers
26
What is logically equivalent to "If Kareena and Parineeti go to the shopping mall then it is raining": If Kareena and Parineeti do not go to the shopping mall then it is not raining. If Kareena and Parineeti do not go to the shopping mall then it is raining. If it ... go to the shopping mall. If it is not raining then Kareena and Parineeti do not go to the shopping mall. None of the above.
asked Dec 4, 2015 in Mathematical Logic makhdoom ghaya 642 views
11 votes
1 answer
27
The Boolean function obtained by adding an inverter to each and every input of an $AND$ gate is: $OR$ $XOR$ $NAND$ $NOR$ None of the above
asked Dec 2, 2015 in Digital Logic makhdoom ghaya 622 views
5 votes
2 answers
28
Let $|z| < 1$. Define $M_{n}(z)= \sum_{i=1}^{10} z^{10^{n}(i - 1)}?$ what is $\prod_{i=0}^{\infty} M_{i}(z)= M_{0}(z)\times M_{1}(z) \times M_{2}(z) \times ...?$ Can't be determined. $1/ (1 - z)$ $1/ (1 + z)$ $1 - z^{9}$ None of the above.
asked Dec 2, 2015 in Numerical Ability makhdoom ghaya 317 views
7 votes
1 answer
29
Consider a circle with a circumference of one unit length. Let $d< \dfrac{1}{6}$. Suppose that we independently throw two arcs, each of length $d$, randomly on this circumference so that each arc is uniformly distributed along the circle circumference. The arc attaches itself exactly to the circumference so that ... equals $(1 - 3d)$ It equals $(1 - 2d)$ It equals $1$ It equals $(1 - d)$ $(1 - d)$
asked Dec 2, 2015 in Numerical Ability makhdoom ghaya 397 views
10 votes
5 answers
30
Consider a $6$-sided die with all sides not necessarily equally likely such that probability of an even number is $P (\left \{2, 4, 6 \right \}) =\dfrac{1}{2}$, probability of a multiple of $3$ is $P (\left \{3, 6 \right \}) = 1/3$ and probability of $1$ ... $P(\left \{5 \right \}) \leq \dfrac{1}{6}$ $P(\left \{ 5 \right \}) \leq \dfrac{1}{3}$ $\text{None of the above.}$
asked Dec 2, 2015 in Probability makhdoom ghaya 816 views
To see more, click for the full list of questions or popular tags.
...