The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged tifr2010
+14
votes
1
answer
1
TIFR2010B40
Which of the following statement is FALSE? All recursive sets are recursively enumerable. The complement of every recursively enumerable sets is recursively enumerable. Every Nonempty 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
by
makhdoom ghaya
Boss
(
30.7k
points)

902
views
tifr2010
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+7
votes
3
answers
2
TIFR2010B39
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
by
makhdoom ghaya
Boss
(
30.7k
points)

453
views
tifr2010
algorithms
pnpnpcnph
+13
votes
6
answers
3
TIFR2010B38
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
by
makhdoom ghaya
Boss
(
30.7k
points)

1k
views
tifr2010
probability
binomialdistribution
+16
votes
2
answers
4
TIFR2010B37
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 ... 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
by
makhdoom ghaya
Boss
(
30.7k
points)

965
views
tifr2010
programming
loopinvariants
+26
votes
5
answers
5
TIFR2010B36
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
by
makhdoom ghaya
Boss
(
30.7k
points)

1.3k
views
tifr2010
graphtheory
degreeofgraph
+12
votes
2
answers
6
TIFR2010B35
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 reverse of string x; ... $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
by
makhdoom ghaya
Boss
(
30.7k
points)

582
views
tifr2010
theoryofcomputation
identifyclasslanguage
+18
votes
3
answers
7
TIFR2010B34
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
by
makhdoom ghaya
Boss
(
30.7k
points)

735
views
tifr2010
theoryofcomputation
regularexpressions
+27
votes
4
answers
8
TIFR2010B33
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 ... 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
by
makhdoom ghaya
Boss
(
30.7k
points)

881
views
tifr2010
databases
relationalalgebra
+12
votes
6
answers
9
TIFR2010B32
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; ... (3), but does not satisfies the requirement (2). Satisfies all the requirement (1), (2), and (3).
asked
Oct 10, 2015
in
Operating System
by
makhdoom ghaya
Boss
(
30.7k
points)

1.1k
views
tifr2010
operatingsystem
processsynchronization
+7
votes
2
answers
10
TIFR2010B31
Consider the following computation rules. Paralleloutermost 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. ... $0$ respectively $0$ and $0$ respectively $w$ and $w$ respectively $w$ and $1$ respectively none of the above
asked
Oct 10, 2015
in
Programming
by
Arjun
Veteran
(
431k
points)

548
views
tifr2010
programming
recursion
+10
votes
2
answers
11
TIFR2010B30
Consider the following program for summing the entries of the array $b$: array $[0 .. N1]$ 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; ... $s = \sum\limits^{i1}_{j=0}b[j] \;\&\; 0 \leq i \leq N$
asked
Oct 8, 2015
in
Programming
by
makhdoom ghaya
Boss
(
30.7k
points)

714
views
tifr2010
programming
loopinvariants
+21
votes
1
answer
12
TIFR2010B29
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, ... 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
by
makhdoom ghaya
Boss
(
30.7k
points)

975
views
tifr2010
searching
+14
votes
3
answers
13
TIFR2010B28
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
by
makhdoom ghaya
Boss
(
30.7k
points)

1k
views
tifr2010
processsynchronization
+14
votes
4
answers
14
TIFR2010B27
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]; ... 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
by
makhdoom ghaya
Boss
(
30.7k
points)

773
views
tifr2010
algorithms
sorting
+34
votes
4
answers
15
TIFR2010B26
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 ... . $O(\log n)$ comparisons but a constant number of additions. $O(n)$ comparisons and $O(n)$ additions, using depthfirst search.
asked
Oct 6, 2015
in
DS
by
makhdoom ghaya
Boss
(
30.7k
points)

2.3k
views
tifr2010
binarysearchtree
+17
votes
3
answers
16
TIFR2010B25
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 ... . 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
by
makhdoom ghaya
Boss
(
30.7k
points)

2k
views
tifr2010
theoryofcomputation
contextfreelanguages
decidability
+6
votes
2
answers
17
TIFR2010B24
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; ... $\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
by
makhdoom ghaya
Boss
(
30.7k
points)

517
views
tifr2010
algorithms
identifyfunction
+11
votes
3
answers
18
TIFR2010B23
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 ... $O\left ( n^{1.5} \right )$ but not better.
asked
Oct 5, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
30.7k
points)

1.1k
views
tifr2010
algorithms
timecomplexity
sorting
+16
votes
3
answers
19
TIFR2010B22
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 ... a nondeterministic pushdown automaton but not by a deterministic pushdown automaton. $L$ cannot be recognized by any pushdown automaton.
asked
Oct 5, 2015
in
Theory of Computation
by
makhdoom ghaya
Boss
(
30.7k
points)

690
views
tifr2010
theoryofcomputation
identifyclasslanguage
+23
votes
3
answers
20
TIFR2010B21
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
by
makhdoom ghaya
Boss
(
30.7k
points)

1.3k
views
tifr2010
digitallogic
booleanalgebra
+8
votes
2
answers
21
TIFR2010A20
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
by
makhdoom ghaya
Boss
(
30.7k
points)

702
views
tifr2010
numericalability
factors
+18
votes
6
answers
22
TIFR2010A19, TIFR2014A6
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 ... $\left(\dfrac{3}{4}\right)$ $\left(\dfrac{5}{6}\right)$ $\left(\dfrac{6}{7}\right)$
asked
Oct 4, 2015
in
Probability
by
makhdoom ghaya
Boss
(
30.7k
points)

2.1k
views
tifr2010
probability
conditionalprobability
tifr2014
+24
votes
4
answers
23
TIFR2010A18
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
by
makhdoom ghaya
Boss
(
30.7k
points)

913
views
tifr2010
sets
+3
votes
1
answer
24
TIFR2010A17
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 ... . $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
by
makhdoom ghaya
Boss
(
30.7k
points)

368
views
tifr2010
numericalability
geometry
+14
votes
1
answer
25
TIFR2010A16
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
by
makhdoom ghaya
Boss
(
30.7k
points)

566
views
tifr2010
linearalgebra
matrices
+7
votes
3
answers
26
TIFR2010A15
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
by
makhdoom ghaya
Boss
(
30.7k
points)

413
views
tifr2010
settheory&algebra
sets
+9
votes
2
answers
27
TIFR2010A14
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
by
makhdoom ghaya
Boss
(
30.7k
points)

491
views
tifr2010
numericalability
numericalcomputation
+6
votes
3
answers
28
TIFR2010A13
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
by
makhdoom ghaya
Boss
(
30.7k
points)

638
views
tifr2010
probability
+22
votes
4
answers
29
TIFR2010A12
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
by
makhdoom ghaya
Boss
(
30.7k
points)

1.1k
views
tifr2010
generatingfunctions
+5
votes
1
answer
30
TIFR2010A11
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$ ... $\left \ \frac{X}{\left \ X \right \}\frac{Y}{\left \ Y \right \} \right \$ None of the above.
asked
Oct 3, 2015
in
Linear Algebra
by
makhdoom ghaya
Boss
(
30.7k
points)

489
views
tifr2010
linearalgebra
vectorspace
Page:
1
2
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged tifr2010
Recent Blog Comments
@!KARAN One may, generally court hear such...
@smsubham thats a big question to me as well. I...
@!KARAN agreed, but what we can do?
RE=regular expressions which is the...
@Akash Ghosh Ofcourse I know that it is regular...
50,737
questions
57,274
answers
198,150
comments
104,800
users