search
Log In
TIFR 2017 Computer Science Questions

Recent questions tagged tifr2017

5 votes
1 answer
1
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)$. Then ... in polynomial time 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
asked Dec 23, 2016 in Algorithms jothee 390 views
15 votes
2 answers
2
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$ ... context free $L(G)$ is infinite $L(G)$ can be recognized by a deterministic push down automaton $L(G)$ is prefix-closed $L(G)$ is recursive
asked Dec 23, 2016 in Theory of Computation jothee 892 views
13 votes
2 answers
3
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 ... maximum degree 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 jothee 812 views
38 votes
6 answers
4
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}$
asked Dec 23, 2016 in Graph Theory jothee 2.4k views
24 votes
3 answers
5
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 jothee 1.2k views
22 votes
2 answers
6
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 ... Which of 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 jothee 1k views
10 votes
3 answers
7
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^*$
asked Dec 23, 2016 in Theory of Computation jothee 686 views
12 votes
4 answers
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 bit). Thus, for $n=3$ ... Gray 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 jothee 1.2k views
14 votes
2 answers
9
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] > max \{A [i-1], A[i+1]\}$, or $A[i] < min \{A[i-1], A[i+1]\}$. What is the time-complexity of the fastest algorithm that takes as input a sorted array $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 jothee 832 views
5 votes
1 answer
10
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
asked Dec 23, 2016 in Mathematical Logic jothee 343 views
12 votes
4 answers
11
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$, then $i==10$ ... is/are 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 jothee 989 views
15 votes
2 answers
12
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\}$ ... following is TRUE? $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
asked Dec 23, 2016 in Theory of Computation jothee 1k views
22 votes
4 answers
13
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 stack, ... pop_ray_pop("(((()((())((((") is executed? $(((($ $))) \ (((($ $)))$ $(((()))$ $()()$
asked Dec 23, 2016 in DS jothee 967 views
3 votes
1 answer
14
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$ ... TRUE? Choose 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 jothee 423 views
32 votes
4 answers
15
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 jothee 1.5k views
9 votes
4 answers
16
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 \text{ if } a, b \geq 2$ ... $\begin{pmatrix} r+s \\ r \end{pmatrix}$ $2^{r-s}$ if $r \geq s$, otherwise $2^{s-r}$
asked Dec 23, 2016 in Algorithms jothee 957 views
8 votes
4 answers
17
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 the last token from the ... has a winning strategy. Edit : Option (D) is : For both $n=7$ and $n=8$, Bharat has a winning strategy. (Source)
asked Dec 23, 2016 in Numerical Ability jothee 899 views
2 votes
1 answer
18
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 obtained by adding ... $S-T$ 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
asked Dec 22, 2016 in Numerical Ability jothee 276 views
6 votes
1 answer
19
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 this program must be TRUE? ... 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 jothee 452 views
24 votes
4 answers
20
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
asked Dec 22, 2016 in Set Theory & Algebra jothee 1.5k views
11 votes
2 answers
21
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 of the following ... $f$ cannot 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
asked Dec 22, 2016 in Set Theory & Algebra jothee 726 views
12 votes
2 answers
22
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 with probability ... $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 jothee 513 views
3 votes
2 answers
23
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 value of $h$. For ... such 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 jothee 466 views
14 votes
2 answers
24
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$, $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 jothee 671 views
14 votes
2 answers
25
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 jothee 543 views
17 votes
3 answers
26
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}$
asked Dec 21, 2016 in Combinatory jothee 1.5k views
15 votes
3 answers
27
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 jothee 1.4k views
4 votes
2 answers
28
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 {2}t$ $2t$ $\left(\dfrac{h}{t}\right)$ $\left(\dfrac{h}{2t}\right)$
asked Dec 21, 2016 in Numerical Ability jothee 496 views
4 votes
2 answers
29
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$ ... $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 jothee 378 views
5 votes
1 answer
30
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
asked Dec 21, 2016 in Numerical Ability jothee 670 views
To see more, click for the full list of questions or popular tags.
...