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. For hardcopy of previous year questions please see
here
Recent questions tagged tifr2017
TIFR 2017 Computer Science Questions
+4
votes
0
answers
1
tifr cut off
What was the cutoff of tifr 2017?
asked
Aug 16, 2017
in
TIFR
by
Shivani Jaiswal
(
189
points)

1.4k
views
tifr2017
+2
votes
1
answer
2
TIFR2017B15
A multivariate polynomial in $n$ variables with integer coefficients has a binary root if it is possible to assign each variable either 0 or 1, so that the polynomial evaluates to 0. For example, the multivariate polynomial $2x_1^3 x_1x_2+2$ has the binary root $(x_1=1, x_2=0)$. ... time is NPhard, but not in NP is in NP, but not in P and not NPhard is both in NP and NPhard
asked
Dec 23, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

199
views
tifr2017
algorithms
pnpnpcnph
+9
votes
1
answer
3
TIFR2017B14
Consider the following grammar $G$ with terminals $\{[, ]\}$, start symbol $S$, and nonterminals $\{A, B, C\}$: $$S \rightarrow AC \mid SS \mid AB$$ $$C \rightarrow SB$$ $$A \rightarrow [$$ $$B \rightarrow ]$$ A language $L$ is called prefixclosed if for ... $L(G)$ is infinite $L(G)$ can be recognized by a deterministic push down automaton $L(G)$ is prefixclosed $L(G)$ is recursive
asked
Dec 23, 2016
in
Theory of Computation
by
jothee
Veteran
(
98.5k
points)

291
views
tifr2017
theoryofcomputation
identifyclasslanguage
+6
votes
2
answers
4
TIFR2017B13
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if the corresponding edges in $G$ are incident on the same vertex. Which of the ... of any vertex in the line graph is at most the maximum degree in the original graph each vertex in the line graph has degree one or two
asked
Dec 23, 2016
in
Graph Theory
by
jothee
Veteran
(
98.5k
points)

323
views
tifr2017
graphtheory
linegraph
+21
votes
4
answers
5
TIFR2017B12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n1)}{2}$
asked
Dec 23, 2016
in
Graph Theory
by
jothee
Veteran
(
98.5k
points)

953
views
tifr2017
graphtheory
counting
+15
votes
2
answers
6
TIFR2017B11
Given that $B(x)$ means "$x$ is a bat", $F(x)$ means "$x$ is a fly", and $E(x, y)$ means "x eats $y$", what is the best English translation of $$ \forall x(F(x) \rightarrow \forall y (E(y, x) \rightarrow B(y)))?$$ all flies eat bats every fly is eaten by some bat bats eat only flies every bat eats flies only bats eat flies
asked
Dec 23, 2016
in
Mathematical Logic
by
jothee
Veteran
(
98.5k
points)

531
views
tifr2017
firstorderlogic
+12
votes
2
answers
7
TIFR2017B10
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements: If every vertex in $G$ has degree at most $d$ then ... the above statements is/are TRUE? Choose from the following options: only i only i and ii only i and iii only ii and iii i, ii, and iii
asked
Dec 23, 2016
in
Graph Theory
by
jothee
Veteran
(
98.5k
points)

374
views
tifr2017
graphtheory
graphcoloring
+6
votes
2
answers
8
TIFR2017B9
Which of the following regular expressions correctly accepts the set of all $0/1$strings with an even (poossibly zero) number of $1$s? $(10^*10^*)^*$ $(0^*10^*1)^*$ $0^*1(10^*1)^*10^*$ $0^*1(0^*10^*10^*)^*10^*$ $(0^*10^*1)^*0^*$
asked
Dec 23, 2016
in
Theory of Computation
by
jothee
Veteran
(
98.5k
points)

263
views
tifr2017
theoryofcomputation
regularexpressions
+7
votes
1
answer
9
TIFR2017B8
For any natural number $n$, an ordering of all binary strings of length $n$ is a Gray code if it starts with $0^n$, and any successive strings in the ordering differ in exactly one bit (the first and last string must also differ by one bit). Thus, for ... code, if two strings are separated by $k$ other strings in the ordering, then they must differ in exactly $k$ bits none of the above
asked
Dec 23, 2016
in
Digital Logic
by
jothee
Veteran
(
98.5k
points)

361
views
tifr2017
digitallogic
binarycodes
graycode
+7
votes
1
answer
10
TIFR2017B7
An array of $n$ distinct elements is said to be unsorted if for every index $i$ such that $ 2 \leq i \leq n1$, either $A[i] > max \{A [i1], A[i+1]\}$, or $A[i] < min \{A[i1], A[i+1]\}$. What is the timecomplexity of the fastest algorithm that takes as input a ... not $O(n)$ $O(n)$ but not $O(\sqrt{n})$ $O(\sqrt{n})$ but not $O(\log n)$ $O(\log n)$ but not $O(1)$ $O(1)$
asked
Dec 23, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

319
views
tifr2017
algorithms
sorting
+2
votes
0
answers
11
TIFR2017B6
Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE? Partial orders cannot be axiomatized in FOL FOL has a complete proof system Natural numbers cannot be axiomatized in FOL Real numbers cannot be axiomatized in FOL Relational numbers cannot be axiomatized in FO
asked
Dec 23, 2016
in
Mathematical Logic
by
jothee
Veteran
(
98.5k
points)

109
views
tifr2017
firstorderlogic
+8
votes
3
answers
12
TIFR2017B5
Consider the following psuedocode fragment, where $y$ is an integer that has been initialized. int i=1 int j=1 while (i<10): j=j*i i=i+1 if (i==y): break end if end while Consider the following statements: $(i==10)$ or $(i==y)$ If $y > 10$, ... TRUE at the end of the while loop? Choose from the following options. i only iii only ii and iii only i, ii, and iii None of the above
asked
Dec 23, 2016
in
Programming
by
jothee
Veteran
(
98.5k
points)

301
views
tifr2017
programming
loopinvariants
+9
votes
2
answers
13
TIFR2017B4
Let $L$ be the language over the alphabet $\{1, 2, 3, (, )\}$ generated by the following grammar (with start symbol $S$, and nonterminals $\{A, B, C\}$): $ S \rightarrow A \: B \: C \\ A \rightarrow ( \\ B \rightarrow 1 ... the following is TRUE? $L$ is finite $L$ is not recursively enumerable $L$ is regular $L$ contains only strings of even length $L$ is contextfree but not regular
asked
Dec 23, 2016
in
Theory of Computation
by
jothee
Veteran
(
98.5k
points)

332
views
tifr2017
theoryofcomputation
identifyclasslanguage
+12
votes
4
answers
14
TIFR2017B3
We have an implementation that supports the following operations on a stack (in the instructions below, $\mathsf{s}$ is the name of the stack). $\mathsf{isempty(s)}$ : returns $\mathsf{True}$ if $\mathsf{s}$ is empty, and $\mathsf{False}$ otherwise. $\mathsf{top(s)}$ : returns the top element of the ... ;(((()((())((((") is executed? $(((($ $))) \ (((($ $)))$ $(((()))$ $()()$
asked
Dec 23, 2016
in
DS
by
jothee
Veteran
(
98.5k
points)

351
views
tifr2017
datastructure
stack
+1
vote
1
answer
15
TIFR2017B2
Consider the following statements: Checking if a given $undirected$ graph has a cycle is in $\mathsf{P}$ Checking if a given $undirected$ graph has a cycle is in $\mathsf{NP}$ Checking if a given $directed$ graph has a cycle is in $\mathsf{P}$ Checking if a given $directed$ ... from the following options. Only i and ii Only ii and iv Only ii, iii, and iv Only i, ii and iv All of them
asked
Dec 23, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

174
views
tifr2017
algorithms
npcompleteness
+20
votes
3
answers
16
TIFR2017B1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$
asked
Dec 23, 2016
in
Graph Theory
by
jothee
Veteran
(
98.5k
points)

535
views
tifr2017
graphtheory
graphcoloring
+3
votes
3
answers
17
TIFR2017A15
Let $T(a, b)$ be the function with two arguments (both nonnegative integral powers of 2) defined by the following reccurence: $ T(a, b) = T \biggl( \frac{a}{2}, b \biggl) +T\biggl( a, \frac{b}{2} \biggl) \quad \quad \text{ if } a, b \geq 2$; $ T(a, 1) = T \biggl( \ ... 2^r+2^s \\ 2^r \end{pmatrix}$ $\begin{pmatrix} r+s \\ r \end{pmatrix}$ $2^{rs}$ if $r \geq s$, otherwise $2^{sr}$
asked
Dec 23, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

222
views
tifr2017
algorithms
recurrence
+6
votes
3
answers
18
TIFR2017A14
Consider the following game with two players, Aditi and Bharat. There are $n$ tokens in a bag. The two players know $n$, and take turns removing tokens from the bag. In each turn, a player can either remove one token or two tokens. The player that removes ... , Aditi has a winning strategy. For both $n=7$ and $n=8$, Aditi has a winning strategy. Bharat never has a winning strategy.
asked
Dec 23, 2016
in
Numerical Ability
by
jothee
Veteran
(
98.5k
points)

470
views
tifr2017
numericalability
logicalreasoning
+2
votes
1
answer
19
TIFR2017A13
A set of points $S \subseteq \mathbb{R}^2$ is convex if for any points $x, \: y \: \in S$, every point on the straight line joining $x$ and $y$ is also in $S$. For two sets of points $S, T \subset \mathbb{R}^2$, define the sum $S+T$ as the set of points ... T$ and $ST$ is convex, but it depends on $S$ and $T$ which one neither $S+T$ nor $ST$ is convex both $S+T$ and $ST$ are convex
asked
Dec 22, 2016
in
Numerical Ability
by
jothee
Veteran
(
98.5k
points)

142
views
tifr2017
numericalability
geometry
+5
votes
1
answer
20
TIFR2017A12
Consider the following program modifying an $n \times n$ square matrix $A$: for i=1 to n: for j=1 to n: temp=A[i][j]+10 A[i][j]=A[j][i] A[j][i]=temp10 end for end for Which of the following statements about the contents of matrix $A$ at the end of this program ... by $10$ the new matrix $A$ is symmetric, that is, $A[i][j]=A[j][i]$ for all $1 \leq i, j \leq n$ $A$ remains unchanged
asked
Dec 22, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

210
views
tifr2017
algorithms
identifyfunction
+12
votes
4
answers
21
TIFR2017A11
Let $f \: \circ \: g$ denote function composition such that $(f \circ g)(x) = f(g(x))$. Let $f: A \rightarrow B$ such that for all $g \: : \: B \rightarrow A$ and $h \: : \: B \rightarrow A$ we have $f \: \circ \: g = f \: \circ ... $f$ is onto (surjective) $f$ is onetoone (injective) $f$ is both onetoone and onto (bijective) the range of $f$ is finite the domain of $f$ is finite
asked
Dec 22, 2016
in
Set Theory & Algebra
by
jothee
Veteran
(
98.5k
points)

741
views
tifr2017
settheory&algebra
functions
+7
votes
2
answers
22
TIFR2017A10
For a set $A$ define $P(A)$ to be the set of all subsets of $A$. For example, if $A = \{1, 2\}$ then $P(A) = \{ \emptyset, \{1, 2\}, \{1\}, \{ 2 \} \}$. Let $A \rightarrow P(A)$ be a function and $A$ is not empty. Which ... ) $f$ cannot be onto (surjective) $f$ is both onetoone and onto (bijective) there is no such $f$ possible if such a function $f$ exists, then $A$ is infinite
asked
Dec 22, 2016
in
Set Theory & Algebra
by
jothee
Veteran
(
98.5k
points)

307
views
tifr2017
settheory&algebra
sets
functions
easy
+7
votes
2
answers
23
TIFR2017A9
Consider the $majority$ function on three bits, $\textbf{maj}: \{0, 1\}^3 \rightarrow \{0, 1\}$ where $\textbf{maj}(x_1, x_2, x_3)=1$ if and only if $x_1+x_2+x_3 \geq 2$. Let $p(\alpha)$ be the probability that the output is 1 when each input is set to 1 independently ... d\alpha} p (\alpha)$? $3 \alpha$ $\alpha^2$ $6\alpha(1\alpha)$ $3\alpha^2 (1\alpha)$ $6\alpha(1\alpha)+\alpha^2$
asked
Dec 21, 2016
in
Probability
by
jothee
Veteran
(
98.5k
points)

216
views
tifr2017
probability
+3
votes
2
answers
24
TIFR2017A8
In a tutorial on geometrical constructions, the teacher asks a student to construct a rightangled triangle ABC where the hypotenuse BC is 8 inches and the length of the perpendicular dropped from A onto the hypotenuse is $h$ inches, and offers various choices for teh value of $h$ ... a triangle NOT exist? 3.90 inches $2 \sqrt{2}$ inches $2 \sqrt{3}$ inches 4.1 inches none of the above
asked
Dec 21, 2016
in
Numerical Ability
by
jothee
Veteran
(
98.5k
points)

226
views
tifr2017
numericalability
geometry
+8
votes
2
answers
25
TIFR2017A7
Consider the sequence $S_0, S_1, S_2, \dots$ defined as follows: $S_0=0, \: S_1=1 \: $ and $S_n=2S_{n1} + S_{n2}$ for $n \geq 2$. Which of the following statements is FALSE? for every $n \geq 1$, $S_{2n}$ is even for every $n \geq 1$, $S_{2n+1}$ is odd for every $n \geq 1$, $S_{3n}$ is multiple of $3$ for every $n \geq 1$, $S_{4n}$ is multiple of $6$ none of the above
asked
Dec 21, 2016
in
Combinatory
by
jothee
Veteran
(
98.5k
points)

304
views
tifr2017
recurrence
+10
votes
3
answers
26
TIFR2017A6
How many distinct words can be formed by permuting the letters of the word $ABRACADABRA$? $\frac{11!}{5! \: 2! \: 2!}$ $\frac{11!}{5! \: 4! }$ $11! \: 5! \: 2! \: 2!\:$ $11! \: 5! \: 4!$ $11! $
asked
Dec 21, 2016
in
Combinatory
by
jothee
Veteran
(
98.5k
points)

237
views
tifr2017
permutationsandcombinations
discretemathematics
easy
+12
votes
3
answers
27
TIFR2017A5
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins? $3^{35}$ $3^{50}2^{50}$ $\begin{pmatrix} 35 \\ 2 \end{pmatrix}$ $\begin{pmatrix} 50 \\ 15 \end{pmatrix}. 3^{35}$ $\begin{pmatrix} 37 \\ 2 \end{pmatrix}$
asked
Dec 21, 2016
in
Combinatory
by
jothee
Veteran
(
98.5k
points)

572
views
tifr2017
permutationsandcombinations
discretemathematics
normal
+9
votes
2
answers
28
TIFR2017A4
Which of the following functions asymptotically grows the fastest as $n$ goes to infinity? $(\log \: \log \: n)!$ $(\log \: \log \: n)^ {\log \: n}$ $(\log \: \log \: n)^{\log \: \log \: \log \: n}$ $(\log \: n)^{\log \: \log \: n}$ $2^{\sqrt{\log \: \log \: n}}$
asked
Dec 21, 2016
in
Algorithms
by
jothee
Veteran
(
98.5k
points)

456
views
tifr2017
algorithms
asymptoticnotations
+4
votes
2
answers
29
TIFR2017A3
On planet TIFR, the acceleration of an object due to gravity is half that on planet earth. An object on planet earth dropped from a height $h$ takes time $t$ to reach the ground. On planet TIFR, how much time would an object dropped from height $h$ take to reach the ground? $\left(\dfrac{t}{\sqrt{2}}\right)$ $\sqrt {2t}$ $2t$ $\left(\dfrac{h}{t}\right)$ $\left(\dfrac{h}{2t}\right)$
asked
Dec 21, 2016
in
Numerical Ability
by
jothee
Veteran
(
98.5k
points)

245
views
tifr2017
numericalability
speedtimedistance
+3
votes
1
answer
30
TIFR2017A2
For vectors $x, \: y$ in $\mathbb{R}^n$, define the inner product $\langle x, y \rangle = \Sigma^n_{i=1} x_iy_i$, and the length of $x$ to be $\ x \ = \sqrt{\langle x, x \rangle}$. Let $a, \: b$ be two vectors in $\mathbb{R} ^n$ so that $\ ... a \$ Which of the above statements must be TRUE of $a, \: b$? Choose from the following options. ii only i and ii iii only iv only iv and v
asked
Dec 21, 2016
in
Linear Algebra
by
jothee
Veteran
(
98.5k
points)

136
views
tifr2017
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
IISc CSA and CDCS written test and interview Experince
IIIT Hyderabad Interview Experience
My failure, Oh wait SUCCESS journey
ALGORITHMS CHECKLIST:
A Failure who got into IISc
Follow @csegate
Gatecse
Recent questions tagged tifr2017
Recent Blog Comments
Sir I didn't get an email for GO classroom, ...
any one with marks less than 125 selected?
Thank you @Arjun Sir, @NamitaAIR1, @Priyanka, ...
Your story is very inspiring for the boys like me ...
So you completed your Btech in 5 yrs? How could ...
36,194
questions
43,647
answers
124,088
comments
42,929
users