search
Log In

Recent questions tagged tifr2010

15 votes
1 answer
1
Which of the following statement is FALSE? All recursive sets are recursively enumerable. The complement of every recursively enumerable sets is recursively enumerable. Every Non-empty recursively enumerable set is the range of some totally recursive function. All finite sets are recursive. The complement of every recursive set is recursive.
asked Oct 11, 2015 in Theory of Computation makhdoom ghaya 1.1k views
8 votes
3 answers
2
Suppose a language $L$ is $\mathbf{NP}$ complete. Then which of the following is FALSE? $L \in \mathbf{NP}$ Every problem in $\mathbf{P}$ is polynomial time reducible to $L$. Every problem in $\mathbf{NP}$ is polynomial time reducible to $L$. The Hamilton cycle problem is polynomial time reducible to $L$. $\mathbf{P} \neq \mathbf{NP}$ and $L \in \mathbf{P}$.
asked Oct 11, 2015 in Algorithms makhdoom ghaya 535 views
16 votes
6 answers
3
Suppose three coins are lying on a table, two of them with heads facing up and one with tails facing up. One coin is chosen at random and flipped. What is the probability that after the flip the majority of the coins(i.e., at least two of them) will have heads facing up? ... $\left(\frac{1}{4}\right)$ $\left(\frac{1}{4}+\frac{1}{8}\right)$ $\left(\frac{2}{3}\right)$
asked Oct 11, 2015 in Probability makhdoom ghaya 1.3k views
20 votes
2 answers
4
Consider the program where $a, b$ are integers with $b > 0$. x:=a; y:=b; z:=0; while y > 0 do if odd (x) then z:= z + x; y:= y - 1; else y:= y % 2; x:= 2 * x; fi Invariant of the loop is a condition which is true before and after every ... will not terminate for some values of $a, b$ but when it does terminate, the condition $z = a * b$ will hold. The program will terminate with $z=a^{b}$
asked Oct 10, 2015 in Programming makhdoom ghaya 1.2k views
28 votes
5 answers
5
In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices? Exactly seven edges leave every vertex. Exactly seven edges leave some vertex. Some vertex has at least seven edges leaving it. The number of edges coming out of vertex is odd. None of the above.
asked Oct 10, 2015 in Graph Theory makhdoom ghaya 1.8k views
13 votes
2 answers
6
Consider the following languages over the alphabet $\{0, 1\}$. $L1=\left \{ x.x^{R}\mid x\in \left \{ 0, 1 \right \}^* \right \}$ $L2=\left \{ x.x\mid x\in \left \{ 0, 1 \right \}^* \right \}$ Where $x^{R}$ ... . Both $L1$ and $L2$ are context free and neither is regular. $L1$ is context free but $L2$ is not context free. Both $L1$ and $L2$ are not context free.
asked Oct 10, 2015 in Theory of Computation makhdoom ghaya 727 views
18 votes
3 answers
7
Let $r, s, t$ be regular expressions. Which of the following identities is correct? $(r + s)^* = r^*s^*$ $r(s + t) = rs + t$ $(r + s)^* = r^* + s^*$ $(rs + r)^* r = r (sr + r)^*$ $(r^*s)^* = (rs)^*$
asked Oct 10, 2015 in Theory of Computation makhdoom ghaya 918 views
28 votes
4 answers
8
In a relational database there are three relations: Customers = C (C Name) Shops = S (S Name) Buys = B (C Name, S Name) Then the Relational Algebra expression ( $\Pi $ is the projection operator). $C-\Pi _{C Name}((C \times S)-B)$ returns the names of ... . Customers who buy from at least two shops. Customers who buy from all shops. Customers who do not buy buy anything at all. None of the above.
asked Oct 10, 2015 in Databases makhdoom ghaya 1.1k views
12 votes
6 answers
9
Consider the following solution (expressed in Dijkstra's guarded command notation) to the mutual exclusion problem. process P1 is begin loop Non_critical_section; while not (Turn=1) do skip od; Critical_section_1; Turn:=2; end loop end ∥ process P2 is begin loop Non_critical_section; while ... and (3), but does not satisfies the requirement (2). Satisfies all the requirement (1), (2), and (3).
asked Oct 10, 2015 in Operating System makhdoom ghaya 1.5k views
9 votes
2 answers
10
Consider the following computation rules. Parallel-outermost rule: Replace all the outermost occurrences of F (i.e., all occurrences of F which do not occur as arguments of other F's) simultaneously. Parallel - innermost rule: Replace all the innermost occurrences of F (i.e.,all ... and $0$ respectively $0$ and $0$ respectively $w$ and $w$ respectively $w$ and $1$ respectively none of the above
asked Oct 10, 2015 in Programming Arjun 700 views
13 votes
2 answers
11
Consider the following program for summing the entries of the array $b$: array $[0 .. N-1]$ of integers, where $N$ is a positive integer. (The symbol '$<>$' denotes 'not equal to'). var i, s: integer; Program i:= 0; s:= 0; [*] while i <> N do s := s + b[i]; i := i + 1; od Which of the ... $s = \sum\limits^{i-1}_{j=0}b[j] \;\&\; 0 \leq i \leq N$
asked Oct 8, 2015 in Programming makhdoom ghaya 1.1k views
24 votes
1 answer
12
Suppose you are given an array $A$ with $2n$ numbers. The numbers in odd positions are sorted in ascending order, that is, $A[1] \leq A[3] \leq \ldots \leq A[2n - 1]$. The numbers in even positions are sorted in descending order, that ... binary search on the entire array. Perform separate binary searches on the odd positions and the even positions. Search sequentially from the end of the array.
asked Oct 6, 2015 in Algorithms makhdoom ghaya 1.6k views
14 votes
4 answers
13
Consider the concurrent program: x: 1; cobegin x:= x + 3 || x := x + x + 2 coend Reading and writing of variables is atomic, but the evaluation of an expression is not atomic. The set of possible values of variable $x$ at the end of the execution of the program is: $\{4\}$ $\{8\}$ $\{4, 7, 10\}$ $\{4, 7, 8, 10\}$ $\{4, 7, 8\}$
asked Oct 6, 2015 in Operating System makhdoom ghaya 1.3k views
17 votes
4 answers
14
Consider the Insertion Sort procedure given below, which sorts an array $L$ of size $n\left ( \geq 2 \right )$ in ascending order: begin for xindex:= 2 to n do x := L [xindex]; j:= xindex - 1; while j > 0 and L[j] > x do L[j + 1]:= L[j]; j:= j - ... insertion sort makes $n (n - 1) / 2 $ comparisons. Insertion Sort makes $n (n - 1) / 2$ comparisons whenever all the elements of $L$ are not distinct.
asked Oct 6, 2015 in Algorithms makhdoom ghaya 991 views
35 votes
4 answers
15
Suppose there is a balanced binary search tree with $n$ nodes, where at each node, in addition to the key, we store the number of elements in the sub tree rooted at that node. Now, given two elements $a$ and $b$, such that $a < b$, we want to find the ... additions. $O(\log n)$ comparisons but a constant number of additions. $O(n)$ comparisons and $O(n)$ additions, using depth-first- search.
asked Oct 6, 2015 in DS makhdoom ghaya 3k views
20 votes
3 answers
16
Which of the following problems is decidable? (Here, CFG means context free grammar and CFL means context free language.) Given a CFG $G$, find whether $L(G) = R$, where $R$ is regular set. Given a CFG $G$, find whether $L(G) = \{\}$. Find whether the intersection of two ... CFL. Find whether CFG $G_1$ and CFG $G_2$ generate the same language, i.e, $L\left (G_1 \right ) = L\left (G_2 \right)$.
asked Oct 6, 2015 in Theory of Computation makhdoom ghaya 2.3k views
9 votes
2 answers
17
Consider the following program operating on four variables $u, v, x, y$, and two constants $X$ and $Y$. x, y, u, v:= X, Y, Y, X; While (x ≠ y) do if (x > y) then x, v := x - y, v + u; else if (y > x) then y, u:= y - x, u + v; od; print ((x + ... $\frac1 2 \times \text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$. The program does none of the above.
asked Oct 6, 2015 in Algorithms makhdoom ghaya 645 views
13 votes
3 answers
18
Suppose you are given $n$ numbers and you sort them in descending order as follows: First find the maximum. Remove this element from the list and find the maximum of the remaining elements, remove this element, and so on, until all elements are exhausted. How many comparisons does this method require in ... $O\left (n \log n \right )$ Same as heap sort. $O\left ( n^{1.5} \right )$ but not better.
asked Oct 5, 2015 in Algorithms makhdoom ghaya 2.3k views
16 votes
3 answers
19
Let $L$ consist of all binary strings beginning with a $1$ such that its value when converted to decimal is divisible by $5$. Which of the following is true? $L$ can be recognized by a deterministic finite state automaton. $L$ can be recognized by a ... by a non-deterministic push-down automaton but not by a deterministic push-down automaton. $L$ cannot be recognized by any push-down automaton.
asked Oct 5, 2015 in Theory of Computation makhdoom ghaya 845 views
25 votes
3 answers
20
For $x \in \{0,1\}$, let $\lnot x$ denote the negation of $x$, that is $\lnot \, x = \begin{cases}1 & \mbox{iff } x = 0\\ 0 & \mbox{iff } x = 1\end{cases}$. If $x \in \{0,1\}^n$, then $\lnot \, x$ denotes the component wise negation of $x$ ... $g(x) = f(x) \land f(\lnot x)$ $g(x) = f(x) \lor f(\lnot x)$ $g(x) = \lnot f(\lnot x)$ None of the above.
asked Oct 5, 2015 in Digital Logic makhdoom ghaya 1.7k views
9 votes
2 answers
21
How many integers from $1$ to $1000$ are divisible by $30$ but not by $16$? $29$ $31$ $32$ $33$ $25$
asked Oct 4, 2015 in Numerical Ability makhdoom ghaya 795 views
21 votes
6 answers
22
Karan tells truth with probability $\dfrac{1}{3}$ and lies with probability $\dfrac{2}{3}.$ Independently, Arjun tells truth with probability $\dfrac{3}{4}$ and lies with probability $\dfrac{1}{4}.$ Both watch a cricket match. Arjun tells you that India won, Karan tells you that India lost. What ... $\left(\dfrac{3}{4}\right)$ $\left(\dfrac{5}{6}\right)$ $\left(\dfrac{6}{7}\right)$
asked Oct 4, 2015 in Probability makhdoom ghaya 2.5k views
28 votes
4 answers
23
Let $X$ be a set of size $n$. How many pairs of sets (A, B) are there that satisfy the condition $A\subseteq B \subseteq X$ ? $2^{n+1}$ $2^{2n}$ $3^{n}$ $2^{n} + 1$ $3^{n + 1}$
asked Oct 4, 2015 in Set Theory & Algebra makhdoom ghaya 1.1k views
5 votes
1 answer
24
Suppose there is a sphere with diameter at least $6$ inches. Through this sphere we drill a hole along a diameter. The part of the sphere lost in the process of drilling the hole looks like two caps joined to a cylinder, where the cylindrical part has length $6$ inches. It turns out that the ... part. $24\pi$ cu. inches $36\pi$ cu. inches $27\pi$ cu. inches $32\pi$ cu. inches $35\pi$ cu. inches
asked Oct 4, 2015 in Numerical Ability makhdoom ghaya 420 views
16 votes
1 answer
25
Let the characteristic equation of matrix $M$ be $\lambda ^{2} - \lambda - 1 = 0$. Then. $M^{-1}$ does not exist. $M^{-1}$ exists but cannot be determined from the data. $M^{-1} = M + I$ $M^{-1} = M - I$ $M^{-1}$ exists and can be determined from the data but the choices (c) and (d) are incorrect.
asked Oct 4, 2015 in Linear Algebra makhdoom ghaya 686 views
7 votes
3 answers
26
Let $A, B$ be sets. Let $\bar{A}$ denote the compliment of set $A$ (with respect to some fixed universe), and $( A - B)$ denote the set of elements in $A$ which are not in $B$. Set $(A - (A - B))$ is equal to: $B$ $A\cap \bar{B}$ $A - B$ $A\cap B$ $\bar{B}$
asked Oct 3, 2015 in Set Theory & Algebra makhdoom ghaya 506 views
10 votes
2 answers
27
A marine biologist wanted to estimate the number of fish in a large lake. He threw a net and found $30$ fish in the net. He marked all these fish and released them into the lake. The next morning he again threw the net and this time caught $40$ fish, of which two were found to be marked. The (approximate) number of fish in the lake is: $600$ $1200$ $68$ $800$ $120$
asked Oct 3, 2015 in Numerical Ability makhdoom ghaya 558 views
7 votes
3 answers
28
A cube whose faces are colored is split into $1000$ small cubes of equal size. The cubes thus obtained are mixed thoroughly. The probability that a cube drawn at random will have exactly two colored faces is: $0.096$ $0.12$ $0.104$ $0.24$ None of the above
asked Oct 3, 2015 in Probability makhdoom ghaya 764 views
23 votes
4 answers
29
The coefficient of $x^{3}$ in the expansion of $(1 + x)^{3} (2 + x^{2})^{10}$ is. $2^{14}$ $31$ $\left ( \frac{3}{3} \right ) + \left ( \frac{10}{1} \right )$ $\left ( \frac{3}{3} \right ) + 2\left ( \frac{10}{1} \right )$ $\left ( \frac{3}{3} \right ) \left ( \frac{10}{1} \right ) 2^{9}$
asked Oct 3, 2015 in Combinatory makhdoom ghaya 1.3k views
6 votes
1 answer
30
The length of a vector $x = (x_{1},\ldots,x_{n})$ is defined as $\left \| x\right \| = \sqrt{\sum ^{n}_{i=1}x^{2}_{i}}$. Given two vectors $x=(x_{1},\ldots, x_{n})$ and $y=(y_{1},\ldots, y_{n})$, which of the following measures of discrepancy between $x$ and $y$ is ... $\left \| \frac{X}{\left \| X \right \|}-\frac{Y}{\left \| Y \right \|} \right \|$ None of the above.
asked Oct 3, 2015 in Linear Algebra makhdoom ghaya 555 views
...