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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Recent questions tagged tifr2012
+2
votes
0
answers
1
tifr 2012
Let T be a tree on n nodes. Consider the following algorithm, that constructs a sequence of leaves u1, u2, . . .. Let u1 be some leaf of tree. Let u2 be a leaf that is farthest from u1. Let u3 be the leaf that is farthest from u2, and, in general, ... , the path connecting u2 and u3 is a longest path in the tree. (D) For some trees, the distance reduces initially, but then stays constant.
asked
Mar 17, 2017
in
Others
by
aantra paul
(
63
points)

106
views
tifr2012
datastructure
+7
votes
4
answers
2
TIFR 2012 Probability
Amar and Akbar both tell the truth with probability $\dfrac{3}{4}$ and lie with probability $\dfrac{1}{4}.$ Amar watches a test match and talks to Akbar about the outcome. Akbar, in turn, tells Anthony, "Amar told me that India won". What probability should Anthony assign to India's ... (a) $\dfrac{9}{16}$ (b) $\dfrac{6}{16}$ (c) $\dfrac{7}{16}$ (d) $\dfrac{10}{16}$
asked
Mar 4, 2017
in
Probability
by
sh!va
Veteran
(
37.3k
points)

307
views
engineeringmathematics
tifr2012
conditionalprobability
+3
votes
0
answers
3
TIFR2012B20
This question concerns the classes P and N P . 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 in ... }\overline{\text{MATCH}} ∈ NP$ $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$ none of the above
asked
Nov 15, 2015
in
Algorithms
by
Arjun
Veteran
(
348k
points)

147
views
tifr2012
algorithms
pnpnpcnph
+15
votes
2
answers
4
TIFR2012B19
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 ... contextfree. 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
by
makhdoom ghaya
Veteran
(
48k
points)

472
views
tifr2012
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+7
votes
2
answers
5
TIFR2012B18
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 ... Both $L_{1}$ and $L_{2}$ are recursive but not contextfree. $L_{1}$ is regular and $L_{2}$ is contextfree. Complement of $L_{2}$ is contextfree.
asked
Nov 2, 2015
in
Theory of Computation
by
makhdoom ghaya
Veteran
(
48k
points)

244
views
tifr2012
theoryofcomputation
identifyclasslanguage
+11
votes
2
answers
6
TIFR2012B17
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 lookahead. $LR(k)$ ... Input string is scanned from left to right once with $k$ symbol to the right as lookahead to give leftmost derivation.
asked
Nov 2, 2015
in
Compiler Design
by
makhdoom ghaya
Veteran
(
48k
points)

297
views
tifr2012
compilerdesign
parsing
+7
votes
1
answer
7
TIFR2012B16
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
by
makhdoom ghaya
Veteran
(
48k
points)

253
views
tifr2012
binarytree
+14
votes
4
answers
8
TIFR2012B15
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 ... 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
by
makhdoom ghaya
Veteran
(
48k
points)

494
views
tifr2012
datastructure
trees
+8
votes
3
answers
9
TIFR2012B14
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 ... 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
by
makhdoom ghaya
Veteran
(
48k
points)

397
views
tifr2012
algorithms
sorting
+14
votes
1
answer
10
TIFR2012B13
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 ... $.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
by
makhdoom ghaya
Veteran
(
48k
points)

342
views
tifr2012
algorithms
sorting
+14
votes
1
answer
11
TIFR2012B12
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
by
makhdoom ghaya
Veteran
(
48k
points)

491
views
tifr2012
linearalgebra
matrices
+13
votes
3
answers
12
TIFR2012B11
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 ... is 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
by
makhdoom ghaya
Veteran
(
48k
points)

361
views
tifr2012
algorithms
searching
+13
votes
3
answers
13
TIFR2012B10
Consider the blockedset 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 ... 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
by
makhdoom ghaya
Veteran
(
48k
points)

581
views
tifr2012
operatingsystem
processsynchronization
semaphore
+10
votes
1
answer
14
TIFR2012B9
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
by
makhdoom ghaya
Veteran
(
48k
points)

366
views
tifr2012
concurrency
+10
votes
2
answers
15
TIFR2012B8
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
by
makhdoom ghaya
Veteran
(
48k
points)

311
views
tifr2012
compilerdesign
parsing
+6
votes
1
answer
16
TIFR2012B7
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 ... to Babu per experiment? $\dfrac{3}{2}\\$ ${\log 5}\\$ $\dfrac{15}{8}\\$ $\dfrac{31}{16}\\$ $2$
asked
Oct 31, 2015
in
Probability
by
makhdoom ghaya
Veteran
(
48k
points)

301
views
tifr2012
probability
expectation
+10
votes
2
answers
17
TIFR2012B6
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
by
makhdoom ghaya
Veteran
(
48k
points)

355
views
tifr2012
algorithms
asymptoticnotations
+5
votes
2
answers
18
TIFR2012B5
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 ... 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
by
makhdoom ghaya
Veteran
(
48k
points)

274
views
tifr2012
settheory&algebra
partialorder
+10
votes
4
answers
19
TIFR2012B4
Let $\wedge $, $\vee $ denote the meet and join operations of lattice. A lattice is called distributive if for all $x, y, z,$ $x\wedge \left ( y\vee z \right )= \left ( x\wedge y \right )\vee \left ( x\wedge 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
by
makhdoom ghaya
Veteran
(
48k
points)

710
views
tifr2012
settheory&algebra
lattice
+14
votes
5
answers
20
TIFR2012B3
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 ... L\left(x\right)\right) \Rightarrow \left(\exists y: \left(J\left(y\right) \Lambda A\left(x, y\right)\right)\right)\right]$
asked
Oct 30, 2015
in
Mathematical Logic
by
makhdoom ghaya
Veteran
(
48k
points)

459
views
tifr2012
mathematicallogic
firstorderlogic
+8
votes
2
answers
21
TIFR2012B2
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
by
makhdoom ghaya
Veteran
(
48k
points)

282
views
tifr2012
graphtheory
degreeofgraph
+5
votes
1
answer
22
TIFR2012B1
For $x, y\in \left\{0, 1\right\}^{n}$, let $x ⊕ y$ be the element of $\left\{0, 1\right\}^{n}$ obtained by the componentwise exclusiveor 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( ... from $\left\{0, 1\right\}^{n}$ to $\left\{0, 1\right\}$ is. $2^{2n}$ $2^{n+1}$ $2^{n1}+1$ $n!$ $2^{n}$
asked
Oct 30, 2015
in
Set Theory & Algebra
by
makhdoom ghaya
Veteran
(
48k
points)

166
views
tifr2012
settheory&algebra
functions
+8
votes
3
answers
23
TIFR2012A20
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
by
makhdoom ghaya
Veteran
(
48k
points)

375
views
tifr2012
probability
+12
votes
2
answers
24
TIFR2012A19
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( ... )$ $\left(\dfrac{1}{1200}\right)$ $\left(\dfrac{1199}{1200}\right)$ $\left(\dfrac{59}{60}\right)$
asked
Oct 30, 2015
in
Probability
by
makhdoom ghaya
Veteran
(
48k
points)

318
views
tifr2012
probability
+3
votes
1
answer
25
TIFR2012A18
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
by
makhdoom ghaya
Veteran
(
48k
points)

183
views
tifr2012
numericalability
ratios
+4
votes
3
answers
26
TIFR2012A17
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, ... as 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
by
makhdoom ghaya
Veteran
(
48k
points)

404
views
tifr2012
probability
+3
votes
2
answers
27
TIFR2012A16
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
by
makhdoom ghaya
Veteran
(
48k
points)

118
views
tifr2012
numericalability
speedtimedistance
+3
votes
2
answers
28
TIFR2012A15
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
by
makhdoom ghaya
Veteran
(
48k
points)

215
views
tifr2012
calculus
maximaminima
+4
votes
3
answers
29
TIFR2012A14
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
by
makhdoom ghaya
Veteran
(
48k
points)

289
views
tifr2012
calculus
limits
+2
votes
2
answers
30
TIFR2012A13
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
by
makhdoom ghaya
Veteran
(
48k
points)

200
views
tifr2012
calculus
maximaminima
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
My GATE journey
Believe..!!
Need a Serious Career Advice
Failure... ?
Applying to NUS
Follow @csegate
Gatecse
Recent questions tagged tifr2012
Recent Blog Comments
Congrats and Best of luck for life ahead :)
Congrats and Best of luck for life ahead :)
Congratulations @Hemant :) I am so happy for u. ...
Have u taken any online coaching ??
Same is for me. I am getting score 584. 2017 ...
34,241
questions
40,932
answers
116,232
comments
39,846
users