Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged tifr2012
7
votes
1
answer
1
TIFR CSE 2012 | Part B | Question: 20
This question concerns the classes $P$ and $NP.$ 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 ... $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$ none of the above
Arjun
asked
in
Graph Theory
Nov 15, 2015
by
Arjun
709
views
tifr2012
graph-theory
graph-matching
p-np-npc-nph
23
votes
2
answers
2
TIFR CSE 2012 | Part B | Question: 19
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 ... . The set of turning machines which do not halt on empty input forms a recursively enumerable set.
makhdoom ghaya
asked
in
Theory of Computation
Nov 2, 2015
by
makhdoom ghaya
2.4k
views
tifr2012
theory-of-computation
recursive-and-recursively-enumerable-languages
13
votes
3
answers
3
TIFR CSE 2012 | Part B | Question: 18
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\}$ ... $L_{2}$ are recursive but not context-free. $L_{1}$ is regular and $L_{2}$ is context-free. Complement of $L_{2}$ is context-free.
makhdoom ghaya
asked
in
Theory of Computation
Nov 2, 2015
by
makhdoom ghaya
1.3k
views
tifr2012
theory-of-computation
identify-class-language
16
votes
2
answers
4
TIFR CSE 2012 | Part B | Question: 17
Which of the following correctly describes $\text{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 ... string is scanned from left to right once with $k$ symbol to the right as look-ahead to give left-most derivation.
makhdoom ghaya
asked
in
Compiler Design
Nov 2, 2015
by
makhdoom ghaya
2.1k
views
tifr2012
compiler-design
parsing
lr-parser
9
votes
1
answer
5
TIFR CSE 2012 | Part B | Question: 16
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$.
makhdoom ghaya
asked
in
DS
Nov 2, 2015
by
makhdoom ghaya
1.6k
views
tifr2012
binary-tree
28
votes
8
answers
6
TIFR CSE 2012 | Part B | Question: 15
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}$ ... . 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}$.
makhdoom ghaya
asked
in
DS
Nov 2, 2015
by
makhdoom ghaya
3.0k
views
tifr2012
data-structures
tree
16
votes
3
answers
7
TIFR CSE 2012 | Part B | Question: 14
Consider the quick sort algorithm on a set of $n$ ... $\Theta (n^{2})$. None of the above.
makhdoom ghaya
asked
in
Algorithms
Nov 2, 2015
by
makhdoom ghaya
2.9k
views
tifr2012
algorithms
sorting
quick-sort
time-complexity
28
votes
4
answers
8
TIFR CSE 2012 | Part B | Question: 13
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 ... $A$ can be sorted with constant $\cdot k^{2}n$ comparisons but not fewer.
makhdoom ghaya
asked
in
Algorithms
Nov 2, 2015
by
makhdoom ghaya
2.6k
views
tifr2012
algorithms
sorting
21
votes
2
answers
9
TIFR CSE 2012 | Part B | Question: 12
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.
makhdoom ghaya
asked
in
Linear Algebra
Nov 1, 2015
by
makhdoom ghaya
2.5k
views
tifr2012
linear-algebra
matrix
21
votes
3
answers
10
TIFR CSE 2012 | Part B | Question: 11
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 : ... $1$ and $2$ are correct. Both Program $2$ and $3$ are correct All the three programs are wrong
makhdoom ghaya
asked
in
Algorithms
Nov 1, 2015
by
makhdoom ghaya
1.9k
views
tifr2012
algorithms
binary-search
26
votes
3
answers
11
TIFR CSE 2012 | Part B | Question: 10
Consider the blocked-set 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 ... exclusion, but allows starvation for any $N\geq 2$ The program achieves mutual exclusion and starvation freedom for any $N\geq 1$
makhdoom ghaya
asked
in
Operating System
Oct 31, 2015
by
makhdoom ghaya
2.8k
views
tifr2012
operating-system
process-synchronization
semaphore
20
votes
1
answer
12
TIFR CSE 2012 | Part B | Question: 9
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$ ... $\left\{7\right\}$ $\left\{3, 5, 7\right\}$ $\left\{3, 7\right\}$ $\left\{3, 5\right\}$
makhdoom ghaya
asked
in
Operating System
Oct 31, 2015
by
makhdoom ghaya
1.8k
views
tifr2012
process-synchronization
operating-system
19
votes
2
answers
13
TIFR CSE 2012 | Part B | Question: 8
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$ ... The parse tree corresponds to Expression (i) Expression (ii) Expression (iv) only Expression (ii), (iii), and (iv) Expression (iii) and (iv) only
makhdoom ghaya
asked
in
Compiler Design
Oct 31, 2015
by
makhdoom ghaya
2.1k
views
tifr2012
compiler-design
parsing
operator-precedence
15
votes
1
answer
14
TIFR CSE 2012 | Part B | Question: 7
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 ... per experiment? $\dfrac{3}{2}\\$ ${\log 5}\\$ $\dfrac{15}{8}\\$ $\dfrac{31}{16}\\$ $2$
makhdoom ghaya
asked
in
Probability
Oct 31, 2015
by
makhdoom ghaya
1.7k
views
tifr2012
probability
expectation
23
votes
4
answers
15
TIFR CSE 2012 | Part B | Question: 6
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}$
makhdoom ghaya
asked
in
Algorithms
Oct 31, 2015
by
makhdoom ghaya
3.5k
views
tifr2012
algorithms
asymptotic-notations
12
votes
3
answers
16
TIFR CSE 2012 | Part B | Question: 5
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. ... $\sqsubseteq $ is neither a partial order nor an equivalence relation.
makhdoom ghaya
asked
in
Set Theory & Algebra
Oct 31, 2015
by
makhdoom ghaya
1.4k
views
tifr2012
set-theory&algebra
partial-order
15
votes
4
answers
17
TIFR CSE 2012 | Part B | Question: 4
Let $\wedge $, $\vee $ denote the meet and join operations of lattice. A lattice is called distributive if for all $x, y, z,$ ... , but not distributive lattice. Distributive lattice. Lattice but not a complete lattice. Under the give ordering positive integers do not form a lattice.
makhdoom ghaya
asked
in
Set Theory & Algebra
Oct 31, 2015
by
makhdoom ghaya
3.4k
views
tifr2012
set-theory&algebra
lattice
25
votes
5
answers
18
TIFR CSE 2012 | Part B | Question: 3
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 ...
makhdoom ghaya
asked
in
Mathematical Logic
Oct 30, 2015
by
makhdoom ghaya
1.6k
views
tifr2012
mathematical-logic
first-order-logic
17
votes
3
answers
19
TIFR CSE 2012 | Part B | Question: 2
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 ... even number of vertices of odd degree. There are odd number of vertices of odd degree. All the vertices are of even degree.
makhdoom ghaya
asked
in
Graph Theory
Oct 30, 2015
by
makhdoom ghaya
2.3k
views
tifr2012
graph-theory
degree-of-graph
17
votes
3
answers
20
TIFR CSE 2012 | Part B | Question: 1
For $x, y\in \left\{0, 1\right\}^{n}$, let $x ⊕ y$ be the element of $\left\{0, 1\right\}^{n}$ obtained by the component-wise exclusive-or of $x$ and $y$. A Boolean function $F:\left\{0, 1\right\}^{n}\rightarrow\left\{0, 1\right\}$ ... $\left\{0, 1\right\}$ is. $2^{2n}$ $2^{n+1}$ $2^{n-1}+1$ $n!$ $2^{n}$
makhdoom ghaya
asked
in
Set Theory & Algebra
Oct 30, 2015
by
makhdoom ghaya
1.9k
views
tifr2012
set-theory&algebra
functions
22
votes
4
answers
21
TIFR CSE 2012 | Part A | Question: 20
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$
makhdoom ghaya
asked
in
Probability
Oct 30, 2015
by
makhdoom ghaya
2.1k
views
tifr2012
probability
conditional-probability
22
votes
2
answers
22
TIFR CSE 2012 | Part A | Question: 19
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$ ... $\left(\dfrac{1}{1200}\right)$ $\left(\dfrac{1199}{1200}\right)$ $\left(\dfrac{59}{60}\right)$
makhdoom ghaya
asked
in
Probability
Oct 30, 2015
by
makhdoom ghaya
2.0k
views
tifr2012
probability
independent-events
4
votes
1
answer
23
TIFR CSE 2012 | Part A | Question: 18
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$
makhdoom ghaya
asked
in
Quantitative Aptitude
Oct 30, 2015
by
makhdoom ghaya
839
views
tifr2012
quantitative-aptitude
ratio-proportion
9
votes
6
answers
24
TIFR CSE 2012 | Part A | Question: 17
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 ... $n$? It will never reach the top. Linear in $n$. Polynomial in $n$. Exponential in $n$. Double exponential in $n$.
makhdoom ghaya
asked
in
Probability
Oct 30, 2015
by
makhdoom ghaya
1.8k
views
tifr2012
probability
binomial-distribution
3
votes
2
answers
25
TIFR CSE 2012 | Part A | Question: 16
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.
makhdoom ghaya
asked
in
Quantitative Aptitude
Oct 30, 2015
by
makhdoom ghaya
685
views
tifr2012
quantitative-aptitude
speed-time-distance
8
votes
2
answers
26
TIFR CSE 2012 | Part A | Question: 15
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
makhdoom ghaya
asked
in
Calculus
Oct 30, 2015
by
makhdoom ghaya
1.3k
views
tifr2012
calculus
differential-equation
7
votes
3
answers
27
TIFR CSE 2012 | Part A | Question: 14
The limit $\displaystyle \lim_{n \rightarrow \infty} \left(\sqrt{n^{2}+n}-n\right)$ equals. $\infty$ $1$ $1 / 2$ $0$ None of the above
makhdoom ghaya
asked
in
Calculus
Oct 30, 2015
by
makhdoom ghaya
1.4k
views
tifr2012
calculus
limits
3
votes
2
answers
28
TIFR CSE 2012 | Part A | Question: 13
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,\quad x \geq 0, y \geq 0, z \geq 0$ is $1 / 3$ $2 / 3$ $1$ $4 / 3$ $4 / 9$
makhdoom ghaya
asked
in
Calculus
Oct 30, 2015
by
makhdoom ghaya
1.1k
views
tifr2012
calculus
maxima-minima
14
votes
2
answers
29
TIFR CSE 2012 | Part A | Question: 12
For the polynomial $p(x)= 8x^{10}-7x^{3}+x-1$ consider the following statements (which may be true or false) It has a root between $[0, 1].$ It has a root between $[0, -1].$ It has no roots outside $(-1, 1).$ Which of the above statements are true? Only (i). Only (i) and (ii). Only (i) and (iii). Only (ii) and (iii). All of (i), (ii) and (iii).
makhdoom ghaya
asked
in
Calculus
Oct 30, 2015
by
makhdoom ghaya
1.1k
views
tifr2012
calculus
polynomials
11
votes
3
answers
30
TIFR CSE 2012 | Part A | Question: 11
Let $N$ be the sum of all numbers from $1$ to $1023$ except the five primes numbers: $2, 3, 11, 17, 31.$ Suppose all numbers are represented using two bytes (sixteen bits). What is the value of the least significant byte (the least significant eight bits) of $N$? $00000000$ $10101110$ $01000000$ $10000000$ $11000000$
makhdoom ghaya
asked
in
Digital Logic
Oct 30, 2015
by
makhdoom ghaya
1.3k
views
tifr2012
digital-logic
number-representation
Page:
1
2
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Central Pollution Control Board CPCB Various Post Recruitment 2023
MP Rajya Sahkari Apex Bank Various Post Recruitment 2023
NITIE MUMBAI throgh GATE
PGCIL recruitment 2023 – Apply Online For 138 Posts through GATE
Admission guidance for GATE CSE 2023
Subjects
All categories
General Aptitude
(2.6k)
Engineering Mathematics
(9.4k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.3k)
Others
(2.5k)
Admissions
(655)
Exam Queries
(848)
Tier 1 Placement Questions
(17)
Job Queries
(77)
Projects
(9)
Unknown Category
(866)
Recent questions tagged tifr2012
Recent Blog Comments
Please upload updated previous year question...
The last hardcopy that was made was for GATE 2022...
overall only 3 post .no post for gen male
for gen GS in the range of 720-750 approx.
can we get 2023 hark copy from amazon?