Register
TIFR 2017 Computer Science Questions

Recent questions tagged tifr2017

5 5 votes
1 1 answer
1.6k
1.6k views
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 eva...
User Avatar
19 19 votes
2 answers 2 answers
5.1k
5.1k views
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$$$...
User Avatar
18 18 votes
2 answers 2 answers
5.0k
5.0k views
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...
User Avatar
67 67 votes
7 answers 7 answers
10.7k
10.7k views
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 d...
User Avatar
34 34 votes
3 answers 3 answers
6.1k
6.1k views
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...
User Avatar
26 26 votes
2 answers 2 answers
3.9k
3.9k views
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 ...
User Avatar
13 13 votes
6 answers 6 answers
3.7k
3.7k views
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...
User Avatar
21 21 votes
4 answers 4 answers
5.4k
5.4k views
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 e...
User Avatar
16 16 votes
2 answers 2 answers
4.8k
4.8k views
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] <...
User Avatar
8 8 votes
1 answers 1 answer
1.8k
1.8k views
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...
User Avatar
21 21 votes
5 answers 5 answers
4.3k
4.3k views
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 whileC...
User Avatar
19 19 votes
2 answers 2 answers
3.9k
3.9k views
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\}$):$ S \rightarrow ...
User Avatar
32 32 votes
5 answers 5 answers
4.5k
4.5k views
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)}$ : ret...
User Avatar
5 5 votes
1 answers 1 answer
1.7k
1.7k views
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{N...
User Avatar
39 39 votes
4 answers 4 answers
6.8k
6.8k views
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 f...
User Avatar
15 15 votes
4 answers 4 answers
3.4k
3.4k views
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) +...
User Avatar
10 10 votes
4 answers 4 answers
5.9k
5.9k views
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 e...
User Avatar
3 3 votes
1 1 answer
1.4k
1.4k views
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 se...
User Avatar
9 9 votes
1 answers 1 answer
2.2k
2.2k views
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 forWhic...
User Avatar
26 26 votes
5 answers 5 answers
7.3k
7.3k views
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 \: :...
User Avatar
14 14 votes
3 answers 3 answers
4.0k
4.0k views
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 \rightarro...
User Avatar
15 15 votes
2 answers 2 answers
2.3k
2.3k views
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$....
User Avatar
4 4 votes
2 answers 2 answers
1.4k
1.4k views
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 ...
User Avatar
15 15 votes
2 answers 2 answers
3.0k
3.0k views
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 F...
User Avatar
15 15 votes
2 answers 2 answers
2.9k
2.9k views
TIFR CSE 2017 | Part A | Question: 6
How many distinct words can be formed by permuting the letters of the word $\text{ABRACADABRA}?$$\frac{11!}{5! \: 2! \: 2!}$$\frac{11!}{5! \: 4! }$$11! \: 5! \: 2! \: 2!\...
User Avatar
19 19 votes
5 answers 5 answers
7.1k
7.1k views
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}$$\bino...
User Avatar
24 24 votes
4 answers 4 answers
6.0k
6.0k views
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)^{\l...
User Avatar
5 5 votes
2 answers 2 answers
1.9k
1.9k views
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...
User Avatar
6 6 votes
2 2 answers
2.1k
2.1k views
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, ...
User Avatar
10 10 votes
1 answers 1 answer
2.8k
2.8k views
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$ kilogramscannot be de...
User Avatar
To see more, click for the full list of questions or popular tags.