Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged tifr2010
15
votes
1
answer
1
TIFR CSE 2010 | Part B | Question: 40
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.
Which of the following statement is FALSE?All recursive sets are recursively enumerable.The complement of every recursively enumerable sets is recursively enumerable.Ever...
makhdoom ghaya
2.5k
views
makhdoom ghaya
asked
Oct 11, 2015
Theory of Computation
tifr2010
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
8
votes
3
answers
2
TIFR CSE 2010 | Part B | Question: 39
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}$.
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...
makhdoom ghaya
1.5k
views
makhdoom ghaya
asked
Oct 11, 2015
Algorithms
tifr2010
algorithms
p-np-npc-nph
+
–
24
votes
6
answers
3
TIFR CSE 2010 | Part B | Question: 38
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}+\frac{1}{8}\right)$ $\left(\frac{2}{3}\right)$
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...
makhdoom ghaya
3.5k
views
makhdoom ghaya
asked
Oct 10, 2015
Probability
tifr2010
probability
binomial-distribution
+
–
23
votes
3
answers
4
TIFR CSE 2010 | Part B | Question: 37
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 ... 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}$
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; fiInvariant of...
makhdoom ghaya
3.3k
views
makhdoom ghaya
asked
Oct 10, 2015
Programming in C
tifr2010
programming
loop-invariants
+
–
37
votes
6
answers
5
TIFR CSE 2010 | Part B | Question: 36
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.
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...
makhdoom ghaya
5.7k
views
makhdoom ghaya
asked
Oct 10, 2015
Graph Theory
tifr2010
graph-theory
degree-of-graph
+
–
15
votes
2
answers
6
TIFR CSE 2010 | Part B | Question: 35
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}$ is the ... 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.
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 ...
makhdoom ghaya
1.8k
views
makhdoom ghaya
asked
Oct 10, 2015
Theory of Computation
tifr2010
theory-of-computation
identify-class-language
+
–
21
votes
3
answers
7
TIFR CSE 2010 | Part B | Question: 34
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)^*$
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...
makhdoom ghaya
2.6k
views
makhdoom ghaya
asked
Oct 10, 2015
Theory of Computation
tifr2010
theory-of-computation
regular-expression
+
–
39
votes
5
answers
8
TIFR CSE 2010 | Part B | Question: 33
In a relational database there are three relations: $Customers = C \textsf{(CName)}$ $Shops = S \textsf{(SName)}$ $Buys = B \textsf{(CName, SName)}$ Then the Relational Algebra expression ( $\Pi $ ... from at least two shops. Customers who buy from all shops. Customers who do not buy buy anything at all. None of the above.
In a relational database there are three relations:$Customers = C \textsf{(CName)}$$Shops = S \textsf{(SName)}$$Buys = B \textsf{(CName, SName)}$Then the Relational Algeb...
makhdoom ghaya
3.7k
views
makhdoom ghaya
asked
Oct 10, 2015
Databases
tifr2010
databases
relational-algebra
+
–
16
votes
6
answers
9
TIFR CSE 2010 | Part B | Question: 32
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 ... ), but does not satisfies the requirement (2). Satisfies all the requirement (1), (2), and (3).
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 no...
makhdoom ghaya
4.6k
views
makhdoom ghaya
asked
Oct 10, 2015
Operating System
tifr2010
operating-system
process-synchronization
+
–
16
votes
2
answers
10
TIFR CSE 2010 | Part B | Question: 31
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 ... $0$ and $0$ respectively $w$ and $w$ respectively $w$ and $1$ respectively none of the above
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 ...
Arjun
1.6k
views
Arjun
asked
Oct 10, 2015
Programming in C
tifr2010
programming
recursion
+
–
16
votes
2
answers
11
TIFR CSE 2010 | Part B | Question: 30
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 ... $s = \sum\limits^{i-1}_{j=0}b[j] \;\&\; 0 \leq i \leq N$
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 ...
makhdoom ghaya
2.7k
views
makhdoom ghaya
asked
Oct 8, 2015
Programming in C
tifr2010
programming
loop-invariants
+
–
26
votes
1
answer
12
TIFR CSE 2010 | Part B | Question: 29
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 ... on the entire array. Perform separate binary searches on the odd positions and the even positions. Search sequentially from the end of the array.
Suppose you are given an array $A$ with $2n$ numbers.The numbers in odd positions are sorted in ascending order, that is, $A \leq A[3] \leq \ldots \leq A[2n - 1]$.The nu...
makhdoom ghaya
4.3k
views
makhdoom ghaya
asked
Oct 6, 2015
Algorithms
tifr2010
algorithms
binary-search
+
–
16
votes
4
answers
13
TIFR CSE 2010 | Part B | Question: 28
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\}$
Consider the concurrent program:x: 1; cobegin x:= x + 3 || x := x + x + 2 coendReading and writing of variables is atomic, but the evaluation of an expression is not atom...
makhdoom ghaya
3.7k
views
makhdoom ghaya
asked
Oct 6, 2015
Operating System
tifr2010
process-synchronization
+
–
22
votes
4
answers
14
TIFR CSE 2010 | Part B | Question: 27
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 + ... $n (n - 1) / 2$ comparisons whenever all the elements of $L$ are not distinct.
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 [xin...
makhdoom ghaya
3.7k
views
makhdoom ghaya
asked
Oct 6, 2015
Algorithms
tifr2010
algorithms
sorting
+
–
49
votes
5
answers
15
TIFR CSE 2010 | Part B | Question: 26
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$ ... $O(n)$ comparisons and $O(n)$ additions, using depth-first- search.
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 ...
makhdoom ghaya
8.6k
views
makhdoom ghaya
asked
Oct 6, 2015
DS
tifr2010
binary-search-tree
+
–
21
votes
3
answers
16
TIFR CSE 2010 | Part B | Question: 25
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 ... whether CFG $G_1$ and CFG $G_2$ generate the same language, i.e, $L\left (G_1 \right ) = L\left (G_2 \right)$.
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 $...
makhdoom ghaya
4.8k
views
makhdoom ghaya
asked
Oct 6, 2015
Theory of Computation
tifr2010
theory-of-computation
context-free-language
decidability
+
–
12
votes
2
answers
17
TIFR CSE 2010 | Part B | Question: 24
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 ... . The program prints $\frac1 2 \times \text{gcd}(X, Y)$ followed by $\frac1 2 \times \text{lcm}(X, Y)$. The program does none of the above.
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 := ...
makhdoom ghaya
1.7k
views
makhdoom ghaya
asked
Oct 6, 2015
Algorithms
tifr2010
algorithms
identify-function
+
–
15
votes
3
answers
18
TIFR CSE 2010 | Part B | Question: 23
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 ... $O\left ( n^{1.5} \right )$ but not better.
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 r...
makhdoom ghaya
4.8k
views
makhdoom ghaya
asked
Oct 5, 2015
Algorithms
tifr2010
algorithms
time-complexity
sorting
+
–
21
votes
2
answers
19
TIFR CSE 2010 | Part B | Question: 22
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$ ... deterministic push-down automaton but not by a deterministic push-down automaton. $L$ cannot be recognized by any push-down automaton.
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 re...
makhdoom ghaya
2.0k
views
makhdoom ghaya
asked
Oct 5, 2015
Theory of Computation
tifr2010
theory-of-computation
identify-class-language
+
–
33
votes
3
answers
20
TIFR CSE 2010 | Part B | Question: 21
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$; that ... $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.
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 \...
makhdoom ghaya
3.4k
views
makhdoom ghaya
asked
Oct 5, 2015
Digital Logic
tifr2010
digital-logic
boolean-algebra
+
–
13
votes
2
answers
21
TIFR CSE 2010 | Part A | Question: 20
How many integers from $1$ to $1000$ are divisible by $30$ but not by $16$? $29$ $31$ $32$ $33$ $25$
How many integers from $1$ to $1000$ are divisible by $30$ but not by $16$?$29$$31$$32$$33$$25$
makhdoom ghaya
1.8k
views
makhdoom ghaya
asked
Oct 4, 2015
Quantitative Aptitude
tifr2010
quantitative-aptitude
factors
+
–
32
votes
6
answers
22
TIFR CSE 2010 | Part A | Question: 19, TIFR CSE 2014 | Part A | Question: 6
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 ... $\left(\dfrac{5}{6}\right)$ $\left(\dfrac{6}{7}\right)$
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...
makhdoom ghaya
5.9k
views
makhdoom ghaya
asked
Oct 4, 2015
Probability
tifr2010
probability
conditional-probability
tifr2014
+
–
40
votes
5
answers
23
TIFR CSE 2010 | Part A | Question: 18
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}$
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}...
makhdoom ghaya
4.6k
views
makhdoom ghaya
asked
Oct 4, 2015
Set Theory & Algebra
tifr2010
set-theory
+
–
7
votes
1
answer
24
TIFR CSE 2010 | Part A | Question: 17
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$ ... $36\pi$ cu. inches $27\pi$ cu. inches $32\pi$ cu. inches $35\pi$ cu. inches
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 ...
makhdoom ghaya
902
views
makhdoom ghaya
asked
Oct 4, 2015
Quantitative Aptitude
tifr2010
quantitative-aptitude
geometry
+
–
19
votes
1
answer
25
TIFR CSE 2010 | Part A | Question: 16
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.
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^...
makhdoom ghaya
12.1k
views
makhdoom ghaya
asked
Oct 4, 2015
Linear Algebra
tifr2010
linear-algebra
matrix
+
–
8
votes
3
answers
26
TIFR CSE 2010 | Part A | Question: 15
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}$
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 i...
makhdoom ghaya
1.5k
views
makhdoom ghaya
asked
Oct 3, 2015
Set Theory & Algebra
tifr2010
set-theory&algebra
set-theory
+
–
13
votes
3
answers
27
TIFR CSE 2010 | Part A | Question: 14
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, ... two were found to be marked. The (approximate) number of fish in the lake is: $600$ $1200$ $68$ $800$ $120$
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 t...
makhdoom ghaya
1.3k
views
makhdoom ghaya
asked
Oct 3, 2015
Quantitative Aptitude
tifr2010
quantitative-aptitude
numerical-computation
+
–
10
votes
3
answers
28
TIFR CSE 2010 | Part A | Question: 13
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
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 w...
makhdoom ghaya
2.4k
views
makhdoom ghaya
asked
Oct 3, 2015
Probability
tifr2010
probability
+
–
29
votes
7
answers
29
TIFR CSE 2010 | Part A | Question: 12
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}$
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{...
makhdoom ghaya
3.2k
views
makhdoom ghaya
asked
Oct 3, 2015
Combinatory
tifr2010
generating-functions
+
–
9
votes
1
answer
30
TIFR CSE 2010 | Part A | Question: 11
The length of a vector $X = (x_{1},\ldots,x_{n})$ is defined as $\left \| X\right \| = \sqrt{\sum \limits^{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 ... $\left \| \frac{X}{\left \| X \right \|}-\frac{Y}{\left \| Y \right \|} \right \|$ None of the above
The length of a vector $X = (x_{1},\ldots,x_{n})$ is defined as$$\left \| X\right \| = \sqrt{\sum \limits^{n}_{i=1}x^{2}_{i}}$$Given two vectors $X=(x_{1},\ldots, x_{n})...
makhdoom ghaya
1.3k
views
makhdoom ghaya
asked
Oct 3, 2015
Linear Algebra
tifr2010
linear-algebra
vector-space
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register