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
TIFR 2017 Computer Science Questions
Recent questions tagged tifr2017
5
votes
1
answer
1
TIFR CSE 2017 | Part B | Question: 15
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$ ... is NP-hard, but not in NP is in NP, but not in P and not NP-hard is both in NP and NP-hard
go_editor
asked
in
Algorithms
Dec 23, 2016
by
go_editor
694
views
tifr2017
algorithms
p-np-npc-nph
17
votes
2
answers
2
TIFR CSE 2017 | Part B | Question: 14
Consider the following grammar $G$ with terminals $\{[, ]\}$, start symbol $S$, and non-terminals $\{A, B, C\}$: $S \rightarrow AC \mid SS \mid AB$ $C \rightarrow SB$ $A \rightarrow [$ $B \rightarrow ]$ A language $L$ is called ... $L(G)$ can be recognized by a deterministic push down automaton $L(G)$ is prefix-closed $L(G)$ is recursive
go_editor
asked
in
Theory of Computation
Dec 23, 2016
by
go_editor
1.9k
views
tifr2017
theory-of-computation
identify-class-language
14
votes
2
answers
3
TIFR CSE 2017 | Part B | Question: 13
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 ... 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
go_editor
asked
in
Graph Theory
Dec 23, 2016
by
go_editor
1.8k
views
tifr2017
graph-theory
line-graph
44
votes
7
answers
4
TIFR CSE 2017 | Part B | Question: 12
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(n-1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$
go_editor
asked
in
Graph Theory
Dec 23, 2016
by
go_editor
4.7k
views
tifr2017
graph-theory
counting
29
votes
3
answers
5
TIFR CSE 2017 | Part B | Question: 11
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
go_editor
asked
in
Mathematical Logic
Dec 23, 2016
by
go_editor
2.2k
views
tifr2017
first-order-logic
23
votes
2
answers
6
TIFR CSE 2017 | Part B | Question: 10
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 ... 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
go_editor
asked
in
Graph Theory
Dec 23, 2016
by
go_editor
2.0k
views
tifr2017
graph-theory
graph-coloring
11
votes
6
answers
7
TIFR CSE 2017 | Part B | Question: 9
Which of the following regular expressions correctly accepts the set of all $0/1$-strings with an even (possibly 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^*$
go_editor
asked
in
Theory of Computation
Dec 23, 2016
by
go_editor
1.6k
views
tifr2017
theory-of-computation
regular-expression
19
votes
4
answers
8
TIFR CSE 2017 | Part B | Question: 8
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 ... two strings are separated by $k$ other strings in the ordering, then they must differ in exactly $k$ bits none of the above
go_editor
asked
in
Digital Logic
Dec 23, 2016
by
go_editor
2.2k
views
tifr2017
digital-logic
binary-codes
gray-code
15
votes
2
answers
9
TIFR CSE 2017 | Part B | Question: 7
An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $ 2 \leq i \leq n-1$, either $A[i] > \text{max} \{A [i-1], A[i+1]\}$, or $A[i] < \text{min} \{A[i-1], A[i+1]\}$. What is the time-complexity of the fastest ... $O(n)$ but not $O(\sqrt{n})$ $O(\sqrt{n})$ but not $O(\log n)$ $O(\log n)$ but not $O(1)$ $O(1)$
go_editor
asked
in
Algorithms
Dec 23, 2016
by
go_editor
1.8k
views
tifr2017
algorithms
sorting
8
votes
1
answer
10
TIFR CSE 2017 | Part B | Question: 6
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 FOL
go_editor
asked
in
Mathematical Logic
Dec 23, 2016
by
go_editor
814
views
tifr2017
first-order-logic
normal
19
votes
5
answers
11
TIFR CSE 2017 | Part B | Question: 5
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 ... 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
go_editor
asked
in
Programming
Dec 23, 2016
by
go_editor
2.0k
views
tifr2017
programming
loop-invariants
17
votes
2
answers
12
TIFR CSE 2017 | Part B | Question: 4
Let $L$ be the language over the alphabet $\{1, 2, 3, (, )\}$ generated by the following grammar (with start symbol $S$, and non-terminals $\{A, B, C\}$ ... $L$ is finite $L$ is not recursively enumerable $L$ is regular $L$ contains only strings of even length $L$ is context-free but not regular
go_editor
asked
in
Theory of Computation
Dec 23, 2016
by
go_editor
1.8k
views
tifr2017
theory-of-computation
identify-class-language
29
votes
5
answers
13
TIFR CSE 2017 | Part B | Question: 3
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 ... ()((())((((") is executed? $(((($ $))) \ (((($ $)))$ $(((()))$ $()()$
go_editor
asked
in
DS
Dec 23, 2016
by
go_editor
2.1k
views
tifr2017
data-structures
stack
3
votes
1
answer
14
TIFR CSE 2017 | Part B | Question: 2
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 ... 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
go_editor
asked
in
Algorithms
Dec 23, 2016
by
go_editor
783
views
tifr2017
algorithms
p-np-npc-nph
34
votes
4
answers
15
TIFR CSE 2017 | Part B | Question: 1
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$
go_editor
asked
in
Graph Theory
Dec 23, 2016
by
go_editor
2.9k
views
tifr2017
graph-theory
graph-coloring
13
votes
4
answers
16
TIFR CSE 2017 | Part A | Question: 15
Let $T(a, b)$ be the function with two arguments (both nonnegative integral powers of 2) defined by the following recurrence: $ T(a, b) = T \left( \frac{a}{2}, b \right) +T\left( a, \frac{b}{2} \right)\quad \quad \quad \text{if } a, b \geq 2$ ... $\begin{pmatrix} r+s \\ r \end{pmatrix}$ $2^{r-s}$ if $r \geq s$, otherwise $2^{s-r}$
go_editor
asked
in
Algorithms
Dec 23, 2016
by
go_editor
1.7k
views
tifr2017
algorithms
recurrence-relation
9
votes
4
answers
17
TIFR CSE 2017 | Part A | Question: 14
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 ... a winning strategy. For both $n=7$ and $n=8$, Bharat has a winning strategy. Bharat never has a winning strategy.
go_editor
asked
in
Analytical Aptitude
Dec 23, 2016
by
go_editor
1.8k
views
tifr2017
analytical-aptitude
logical-reasoning
3
votes
1
answer
18
TIFR CSE 2017 | Part A | Question: 13
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 ... is convex, but it depends on $S$ and $T$ which one neither $S+T$ nor $S-T$ is convex both $S+T$ and $S-T$ are convex
go_editor
asked
in
Quantitative Aptitude
Dec 22, 2016
by
go_editor
527
views
tifr2017
quantitative-aptitude
geometry
7
votes
1
answer
19
TIFR CSE 2017 | Part A | Question: 12
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]=temp-10 end for end for Which of the following statements about the contents of matrix $A$ at the end of ... 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
go_editor
asked
in
Algorithms
Dec 22, 2016
by
go_editor
950
views
tifr2017
algorithms
identify-function
26
votes
4
answers
20
TIFR CSE 2017 | Part A | Question: 11
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$ ... ) $f$ is one-to-one (injective) $f$ is both one-to-one and onto (bijective) the range of $f$ is finite the domain of $f$ is finite
go_editor
asked
in
Set Theory & Algebra
Dec 22, 2016
by
go_editor
2.8k
views
tifr2017
set-theory&algebra
functions
12
votes
2
answers
21
TIFR CSE 2017 | Part A | Question: 10
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 ... be onto (surjective) $f$ is both one-to-one and onto (bijective) there is no such $f$ possible if such a function $f$ exists, then $A$ is infinite
go_editor
asked
in
Set Theory & Algebra
Dec 22, 2016
by
go_editor
1.5k
views
tifr2017
set-theory&algebra
set-theory
functions
easy
13
votes
2
answers
22
TIFR CSE 2017 | Part A | Question: 9
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 ... $3 \alpha$ $\alpha^2$ $6\alpha(1-\alpha)$ $3\alpha^2 (1-\alpha)$ $6\alpha(1-\alpha)+\alpha^2$
go_editor
asked
in
Probability
Dec 21, 2016
by
go_editor
915
views
tifr2017
probability
4
votes
2
answers
23
TIFR CSE 2017 | Part A | Question: 8
In a tutorial on geometrical constructions, the teacher asks a student to construct a right-angled 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 ... NOT exist? 3.90 inches $2 \sqrt{2}$ inches $2 \sqrt{3}$ inches 4.1 inches none of the above
go_editor
asked
in
Quantitative Aptitude
Dec 21, 2016
by
go_editor
706
views
tifr2017
quantitative-aptitude
geometry
15
votes
2
answers
24
TIFR CSE 2017 | Part A | Question: 7
Consider the sequence $S_0, S_1, S_2, \dots$ defined as follows: $S_0=0, \: S_1=1 \: $ and $S_n=2S_{n-1} + S_{n-2}$ 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$ ... 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
go_editor
asked
in
Combinatory
Dec 21, 2016
by
go_editor
1.3k
views
tifr2017
recurrence-relation
14
votes
2
answers
25
TIFR CSE 2017 | Part A | Question: 6
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! $
go_editor
asked
in
Combinatory
Dec 21, 2016
by
go_editor
1.4k
views
tifr2017
combinatory
discrete-mathematics
easy
18
votes
4
answers
26
TIFR CSE 2017 | Part A | Question: 5
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}$ $\binom{35}{2}$ $\binom{50}{15} \cdot 3^{35}$ $\binom{37}{2}$
go_editor
asked
in
Combinatory
Dec 21, 2016
by
go_editor
3.1k
views
tifr2017
combinatory
discrete-mathematics
normal
balls-in-bins
21
votes
3
answers
27
TIFR CSE 2017 | Part A | Question: 4
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}}$
go_editor
asked
in
Algorithms
Dec 21, 2016
by
go_editor
3.0k
views
tifr2017
algorithms
asymptotic-notations
5
votes
2
answers
28
TIFR CSE 2017 | Part A | Question: 3
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 ... $\sqrt {2}t$ $2t$ $\left(\dfrac{h}{t}\right)$ $\left(\dfrac{h}{2t}\right)$
go_editor
asked
in
Quantitative Aptitude
Dec 21, 2016
by
go_editor
817
views
tifr2017
quantitative-aptitude
speed-time-distance
6
votes
2
answers
29
TIFR CSE 2017 | Part A | Question: 2
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$ ... $a, \: b$? Choose from the following options. ii only i and ii iii only iv only iv and v
go_editor
asked
in
Linear Algebra
Dec 21, 2016
by
go_editor
1.1k
views
tifr2017
linear-algebra
vector-space
5
votes
1
answer
30
TIFR CSE 2017 | Part A | Question: 1
A suitcase weighs one kilogram plus half of its weight. How much does the suitcase weigh? $1.3333$... kilograms $1.5$ kilograms $1.666$... kilograms $2$ kilograms cannot be determined from the given data
go_editor
asked
in
Quantitative Aptitude
Dec 21, 2016
by
go_editor
1.2k
views
tifr2017
quantitative-aptitude
fraction
normal
To see more, click for the
full list of questions
or
popular tags
.
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
Delhi Subordinate Services Selection Board
IIT GATE Admission Online Form 2023
All about M.Tech. and Research Admissions at IITP
IIT JAM Admission Online Form 2023
All about M.Tech. and Research Admissions at IITGn
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(8.9k)
Digital Logic
(3.2k)
Programming and DS
(5.7k)
Algorithms
(4.4k)
Theory of Computation
(6.5k)
Compiler Design
(2.2k)
Operating System
(4.8k)
Databases
(4.4k)
CO and Architecture
(3.6k)
Computer Networks
(4.4k)
Non GATE
(1.2k)
Others
(2.3k)
Admissions
(644)
Exam Queries
(836)
Tier 1 Placement Questions
(17)
Job Queries
(72)
Projects
(9)
Unknown Category
(851)
Recent questions tagged tifr2017
Recent Blog Comments
Sure will provide it as soon as possible.
sir in the excel sheet of shedule of test link of...
The spreadsheet is up to date.
Can somebody give the details of how many topic...
@kabir5454 Anyway you should not be looking for...