TIFR PHD CS & SS 2020
Question 1 |
Two balls are drawn uniformly at random without replacement from a set of five balls numbered 1, 2, 3, 4, 5. What is the expected value of the larger number on the balls drawn?
2.5 | |
3 | |
3.5 | |
4 | |
None of the above |
Question 2 |
Let M be a real nXn matrix such that for every non-zero vector xεRn, we have xT Mx > 0. Then
Such an M cannot exist. | |
Such M s exist and their rank is always n. | |
Such M s exist, but their eigenvalues are always real. | |
No eigenvalue of any such M can be real. | |
None of the above. |
Question 5 |
Let A be an nXn invertible matrix with real entries whose column sums are all equal to 1. Consider the following statements:
(1) Every column in the matrix A2 sums to 2.
(2) Every column in the matrix A3 sums to 3.
(3) Every column in the matrix A-1 sums to 1.
Which of the following is TRUE?
(1) Every column in the matrix A2 sums to 2.
(2) Every column in the matrix A3 sums to 3.
(3) Every column in the matrix A-1 sums to 1.
Which of the following is TRUE?
none of the statements (1), (2), (3) is correct | |
statement (1) is correct but not statements (2) or (3) | |
statement (2) is correct but not statements (1) or (3) | |
statement (3) is correct but not statements (1) or (2) | |
all the 3 statements (1), (2), and (3) are correct
|
Question 6 |
What is the maximum number of regions that the plane R2 can be partitioned into using 10 lines?
Hint: Let A(n) be the maximum number of partitions that can be made by n lines. Observe that A(0) = 1, A(2) = 2, A(2) = 4 etc. Come up with a recurrence equation for A(n).
Hint: Let A(n) be the maximum number of partitions that can be made by n lines. Observe that A(0) = 1, A(2) = 2, A(2) = 4 etc. Come up with a recurrence equation for A(n).
25 | |
50 | |
55 | |
56 | |
1024 |
Question 7 |
A lottery chooses four random winners. What is the probability that at least three of them are born on the same day of the week? Assume that the pool of candidates is so large that each winner is equally likely to be born on any of the seven days of the week independent of the other winners
17 / 2401
| |
48 / 2401
| |
105 / 2401 | |
175 / 2401 | |
294 / 2401 |
Question 8 |
Consider a function f : [0, 1] --> [0, 1] which is twice differentiable in (0, 1). Suppose it has exactly one global maximum and exactly one global minimum inside (0, 1). What can you say about the behaviour of the first derivative f' and and second derivative f'' on (0, 1) (give the most precise answer)?
f' is zero at exactly two points, f'' need not be zero anywhere | |
f' is zero at exactly two points, f'' is zero at exactly one point | |
f' is zero at at least two points, f'' is zero at exactly one point | |
f' is zero at at least two points, f'' is zero at at least one point | |
f' is zero at at least two points, f'' is zero at at least two points |
Question 9 |
A contiguous part, i.e., a set of adjacent sheets, is missing from Tharoor’s GRE preparation book. The number on the first missing page is 183, and it is known that the number on the last missing page has the same three digits, but in a different order. Note that every sheet has two pages, one at the front and one at the back. How many pages are missing from Tharoor’s book?
45 | |
135 | |
136 | |
198 | |
450 |
Question 10 |
In a certain year there were exactly four Fridays and exactly four Mondays in January. On what day of the week did the 20th of January fall that year (recall that January has 31 days)?
Sunday | |
Monday | |
Wednesday | |
Friday | |
None of the others
|
Question 11 |
Suppose we toss m = 3 labelled balls into n = 3 numbered bins. Let A be the event that the first bin is empty while B be the event that the second bin is empty. P(A) and P(B) denote their respective probabilities. Which of the following is true?
P(A) > P(B) | |
P(A) = 1/27 | |
P(A) > P(A|B) | |
P(A) < P(A|B) | |
None of the above |
Question 12 |
The hour needle of a clock is malfunctioning and travels in the anti-clockwise direction, i.e., opposite to the usual direction, at the same speed it would have if it was working correctly. The minute needle is working correctly. Suppose the the two needles show the correct time at 12 noon, thus both needles are together at the 12 mark. After how much time do the two needles meet again?
10/11 hour | |
11/12 hour | |
12/13 hour | |
19/22 hour | |
One hour |
Question 13 |
What is the area of the largest rectangle that can be inscribed in a circle of radius R?
R2/2 | |
π X R2/2 | |
R2 | |
2R2 | |
None of the above |
Question 14 |
A ball is thrown directly upwards from the ground at a speed of 10 ms−1, on a planet where the gravitational acceleration is 10 ms−2. Consider the following statements:
1. The ball reaches the ground exactly 2 seconds after it is thrown up
2. The ball travels a total distance of 10 metres before it reaches the ground
3. The velocity of the ball when it hits the ground is 10 ms−1
What can you say now?
1. The ball reaches the ground exactly 2 seconds after it is thrown up
2. The ball travels a total distance of 10 metres before it reaches the ground
3. The velocity of the ball when it hits the ground is 10 ms−1
What can you say now?
Only Statement 1 is correct | |
Only Statement 2 is correct | |
Only Statement 3 is correct | |
None of the Statements 1, 2 or 3 is correct | |
All of the Statements 1, 2 and 3 are correct |
Question 15 |
The sequence s0, s1, . . . , s9 is defined as follows:
what is s0

what is s0
81 | |
95 | |
100 | |
121 | |
190 |
Question 17 |
Consider the following statements.
1. The intersection of two context-free languages is always context-free.
2. The super-set of a context-free language is never regular.
3. The subset of a decidable language is always decidable.
4. Let Σ ≡ {a, b, c} . Let L ⊆ Σ be the language of all strings in which either the number of occurrences of a is the same as the number of occurrences of b OR the number of occurrences of b is the same as the number of occurrences of c. Then, L is not context-free.
Which of the above statements are true?
1. The intersection of two context-free languages is always context-free.
2. The super-set of a context-free language is never regular.
3. The subset of a decidable language is always decidable.
4. Let Σ ≡ {a, b, c} . Let L ⊆ Σ be the language of all strings in which either the number of occurrences of a is the same as the number of occurrences of b OR the number of occurrences of b is the same as the number of occurrences of c. Then, L is not context-free.
Which of the above statements are true?
Only (1) | |
Only (1) and (2) | |
Only (1),(2) and (3) | |
Only (4) | |
None of (1), (2), (3), (4) are true |
Question 18 |
Consider the (decimal) number 182, whose binary representation is 10110110. How many positive integers are there in the following set?
{n ∈ N : n ≤ 182 and n has exactly four ones in its binary representation}
{n ∈ N : n ≤ 182 and n has exactly four ones in its binary representation}
91 | |
70 | |
54 | |
35 | |
27 |
Question 19 |
A clamp gate is an analog gate parametrized by two real numbers a and b, and denoted as clampa,b. It takes as input two non-negative real numbers x and y. Its output is defined as
Consider circuits composed only of clamp gates, possibly parametrized by different pairs (a, b) of real numbers. How many clamp gates are needed to construct a circuit that on input non-negative reals x and y outputs the maximum of x and y?

Consider circuits composed only of clamp gates, possibly parametrized by different pairs (a, b) of real numbers. How many clamp gates are needed to construct a circuit that on input non-negative reals x and y outputs the maximum of x and y?
1 | |
2 | |
3 | |
4 | |
No circuit composed only of clamp gates can compute the max function. |
Question 20 |

a | |
b | |
c | |
d | |
e |
Question 21 |
Consider the context-free grammar below (s denotes the empty string, alphabet is {a, b}):
S → ε|aSb|bSa|SS.
What language does it generate?
S → ε|aSb|bSa|SS.
What language does it generate?
(ab)∗ + (ba)∗ | |
(abba)∗ +(baab)∗ | |
(aabb)∗ + (bbaa)∗ | |
Strings of the form anbn or bnan, n any positive integer | |
Strings with equal numbers of a and b |
Question 22 |
Consider the following algorithm (Note: For positive integers p, q, p/q denotes the floor of the rational number p/q , assume that given p, q, p/q can be computed in one step):
Input: Two positive integers a, b, a ≥ b.
Output: A positive integer g. while (b > 0) {
x = a - (a/b)*b; a = b;
b = x;
}
g = a;
Suppose K is an upper bound on a. How many iterations does the above algorithm take in the worst case?
Input: Two positive integers a, b, a ≥ b.
Output: A positive integer g. while (b > 0) {
x = a - (a/b)*b; a = b;
b = x;
}
g = a;
Suppose K is an upper bound on a. How many iterations does the above algorithm take in the worst case?
Θ(log K) | |
Θ(K) | |
Θ(K log K) | |
Θ(K2) | |
Θ(2K) |
Question 23 |
Jobs keep arriving at a processor. A job can have an associated time length as well as a priority tag. New jobs may arrive while some earlier jobs are running. Some jobs may keep running indefinitely. A starvation free job-scheduling policy guarantees that no job waits indefinitely for service. Which of the following job-scheduling policies is starvation free?
Round-robin | |
Shortest job first | |
Priority queuing | |
Latest job first | |
None of the others |
Question 24 |
A particular Panini-Backus-Naur Form definition for a < word > is given by the following rules:
Which of the following lexical entities can be derived from < word >?
I. word
II. words
III. c22

Which of the following lexical entities can be derived from < word >?
I. word
II. words
III. c22
None of I, II or III | |
I and II only | |
I and III only | |
II and III only | |
I, II and III |
Question 25 |
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of n) asymptotically?


a | |
b | |
c | |
d | |
e |
Question 26 |
Which of the following graphs are bipartite?


Only (1) | |
Only (2) | |
Only (2) and (3) | |
None of (1),(2), (3) | |
All of (1), (2), (3)
|
Question 27 |
Given the pseudocode below for the function remains(), which of the following statements is true about the output, if we pass it a positive integer n > 2?
int remains(int n)
{
int x = n;
for (i=(n-1);i>1;i--) { x = x i;
}
return x;
}
int remains(int n)
{
int x = n;
for (i=(n-1);i>1;i--) { x = x i;
}
return x;
}
Output is always 0 | |
Output is always 1 | |
Output is 0 only if n is NOT a prime number | |
Output is 1 only if n is a prime number | |
None of the above |
Question 28 |
Let G be an undirected graph. An Eulerian cycle of G is a cycle that traverses each edge of G exactly once. A Hamiltonian cycle of G is a cycle that traverses each vertex of G exactly once. Which of the following must be true?
Checking if G has an Eulerian cycle can be done in polynomial time | |
Deciding if G has a Hamiltonian cycle is not NP-complete | |
If G has an Eulerian cycle, then it has a Hamiltonian cycle | |
A complete graph always has both an Eulerian cycle and a Hamiltonian cycle | |
All of the other statements are true |
Question 29 |
The figure below describes the network of streets in a city where Motabhai sells pakoras from his cart. The number next to an edge is the time (in minutes) taken to traverse the corresponding street.
At present the cart is required to start at point s and, after visiting each street at least once, reach point t. For example, Motabhai can visit the streets in the following order
s − a − c − s − e − c − d − a − b − d − f − e − d − b − t − f − d − t
in order to go from s to t. Note that the streets b, d and d, f are both visited twice in this strategy. The total time taken for this trip is 440 minutes [which is, 380 (the sum of the traversal times of all streets in the network) + 60 (the sum of the traversal times of streets {b, d} and {d, f })].
Motabhai now wants the cart to return to s at the end of the trip. So the previous strategy is not valid, and he must find a new strategy. How many minutes will Motabhai now take if he uses an optimal strategy?
Hint: s, t, b and f are the only odd degree nodes in the figure above.

At present the cart is required to start at point s and, after visiting each street at least once, reach point t. For example, Motabhai can visit the streets in the following order
s − a − c − s − e − c − d − a − b − d − f − e − d − b − t − f − d − t
in order to go from s to t. Note that the streets b, d and d, f are both visited twice in this strategy. The total time taken for this trip is 440 minutes [which is, 380 (the sum of the traversal times of all streets in the network) + 60 (the sum of the traversal times of streets {b, d} and {d, f })].
Motabhai now wants the cart to return to s at the end of the trip. So the previous strategy is not valid, and he must find a new strategy. How many minutes will Motabhai now take if he uses an optimal strategy?
Hint: s, t, b and f are the only odd degree nodes in the figure above.
430 | |
440 | |
460 | |
470 | |
480 |
Question 31 |
Consider a discrete-time system which in response to input sequence x[n] (n integer) outputs the sequence y[n] such that
Suppose |α| < 1. Is the system linear, time-invariant, bounded input bounded output (BIBO) stable?

Suppose |α| < 1. Is the system linear, time-invariant, bounded input bounded output (BIBO) stable?
Linear, time-invariant, BIBO stable | |
Non-linear, time-invariant, BIBO stable | |
Linear, time-variant, BIBO unstable | |
Non-linear, time-variant, BIBO stable | |
Cannot be determined from the information given |
Question 33 |
Balls are drawn one after the other uniformly at random without replacement from a set of eight balls numbered 1, 2, . . . , 8 until all balls drawn. What is the expected number of balls whose value match their ordinality (i.e., their position in the order in which balls were drawn)?
Hint: what is the probability that the i-th ball is drawn at the i-th draw? Now can you use linearity of expectation to solve the problem?
Hint: what is the probability that the i-th ball is drawn at the i-th draw? Now can you use linearity of expectation to solve the problem?
1 | |
1.5 | |
2 | |
2.5 | |
None of the above |
Question 34 |
Let f, g : R --> R be two functions that are continuous and differentiable. Consider the following statements:
1. min{f, g} is continuous
2. max{f, g} is continuous
3. max{f, g} is differentiable
Which of the following is TRUE?
1. min{f, g} is continuous
2. max{f, g} is continuous
3. max{f, g} is differentiable
Which of the following is TRUE?
Only statement 1 is correct | |
Only statement 2 is correct | |
Only statement 3 is correct | |
Only statements 1 and 2 are correct | |
None of the above |
Question 35 |

g(x) is aperiodic | |
g(x) is periodic with period 1 | |
g(x) is periodic with period 1 | |
The value of h determines whether or not g(x) is periodic | |
None of the above |
Question 36 |
For all values of r > 0, the area of the set of all points outside the unit square whose Euclidean distance to the unit square is less than r is:

a | |
b | |
c | |
d | |
e |
Question 38 |
Suppose that Dice 1 has five faces numbered 1 to 5, each of which is equally likely to occur once the dice is rolled. Dice 2 similarly has eight equally likely faces numbered 1 to 8. Suppose that the two dice are rolled, and the sum is equal to 8. Conditioned on this, what is the chance that the Dice 1 rolled a number less than or equal to 2?
1/4 | |
1/3 | |
1/2 | |
2/7 | |
2/5 |
Question 39 |
Let A be an nXn matrix with the the property that Am = 0 for some mεN. Consider the following statements:
1. At least one entry of A is zero
2. All eigenvalues of A are zero
3. All diagonal entries of A are zero
Which of the following is TRUE?
1. At least one entry of A is zero
2. All eigenvalues of A are zero
3. All diagonal entries of A are zero
Which of the following is TRUE?
Only statement 1 is correct | |
Statement 2 alone is correct | |
Only statement 3 is correct | |
Only statements 1 and 2 are correct | |
Only statements 2 and 3 are correct
|
Question 40 |
Consider two independent random variables (U1, U2) both are uniformly distributed between [0, 1]. The conditional expectation
E[(U1 + U2)| max(U1, U2) ≥ 0.5]
equals
E[(U1 + U2)| max(U1, U2) ≥ 0.5]
equals
7/6 | |
8/7 | |
6/7 | |
1.1 | |
None of the above |
Question 41 |
Suppose that X is a real valued random variable and E[exp X] = 2. Then, which of the following must be TRUE?
Hint: (exp(x) + exp(y))/2 ≥ exp((x + y)/2).
Hint: (exp(x) + exp(y))/2 ≥ exp((x + y)/2).
E[X] < ln 2 | |
E[X] > ln 2 | |
E[X] ≥ ln 2 | |
E[X] ≤ ln 2 | |
None of the above |
Question 42 |
Consider a unit disc D. Let a point x be chosen uniformly on D and let the random distance to x from the center of D be R. Which of the following is TRUE?
R2 is uniformly distributed in [0, 1] | |
πR2 is uniformly distributed in [0, 1] | |
π R2 is uniformly distributed in [0, 1] | |
2πR2 is uniformly distributed in [0, 1] | |
None of the above |
Question 43 |
Alice and Bob have one coin each with probability of Heads p and q, respectively. In each round, both Alice and Bob independently toss their coin once, and the game stops if one of them gets a Heads and the other gets a Tails. If they both get either Heads or both get Tails in any round, the game continues. Let R be the expected number of rounds by which the game stops. Which of the following is TRUE?
R=1/(p+q-2pq) | |
R=1/(p+q-p2q | |
R is independent of p and q | |
R=1/(1+2pq-p-q) | |
None of the above |
Question 44 |

Only statement 1 is correct | |
Only statement 2 is correct | |
Only statements 1 and 2 are correct | |
All Statements 1, 2 and 3 are correct | |
None of the above |
There are 45 questions to complete.