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 nonzero vector xεR^{n}, we have x^{T} 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 A^{2} sums to 2.
(2) Every column in the matrix A^{3} 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 A^{2} sums to 2.
(2) Every column in the matrix A^{3} 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 R^{2} 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(AB)  
P(A) < P(AB)  
None of the above 
Question 12 
The hour needle of a clock is malfunctioning and travels in the anticlockwise 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?
R^{2}/2  
π X R^{2}/2  
R^{2}  
2R^{2}  
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 contextfree languages is always contextfree.
2. The superset of a contextfree 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 contextfree.
Which of the above statements are true?
1. The intersection of two contextfree languages is always contextfree.
2. The superset of a contextfree 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 contextfree.
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 clamp_{a,b}. It takes as input two nonnegative 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 nonnegative 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 nonnegative 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 contextfree grammar below (s denotes the empty string, alphabet is {a, b}):
S → εaSbbSaSS.
What language does it generate?
S → εaSbbSaSS.
What language does it generate?
(ab)^{∗} + (ba)^{∗}  
(abba)^{∗} +(baab)^{∗}  
(aabb)^{∗} + (bbaa)^{∗}  
Strings of the form a^{n}b^{n} or b^{n}a^{n}, 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)  
Θ(K^{2})  
Θ(2^{K}) 
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 jobscheduling policy guarantees that no job waits indefinitely for service. Which of the following jobscheduling policies is starvation free?
Roundrobin  
Shortest job first  
Priority queuing  
Latest job first  
None of the others 
Question 24 
A particular PaniniBackusNaur 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=(n1);i>1;i) { x = x i;
}
return x;
}
int remains(int n)
{
int x = n;
for (i=(n1);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 NPcomplete  
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 discretetime system which in response to input sequence x[n] (n integer) outputs the sequence y[n] such that
Suppose α < 1. Is the system linear, timeinvariant, bounded input bounded output (BIBO) stable?
Suppose α < 1. Is the system linear, timeinvariant, bounded input bounded output (BIBO) stable?
Linear, timeinvariant, BIBO stable  
Nonlinear, timeinvariant, BIBO stable  
Linear, timevariant, BIBO unstable  
Nonlinear, timevariant, 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 ith ball is drawn at the ith draw? Now can you use linearity of expectation to solve the problem?
Hint: what is the probability that the ith ball is drawn at the ith 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 A^{m} = 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?
R^{2} is uniformly distributed in [0, 1]  
πR^{2} is uniformly distributed in [0, 1]  
π R^{2} is uniformly distributed in [0, 1]  
2πR^{2} 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+q2pq)  
R=1/(p+qp^{2}^{q}  
R is independent of p and q  
R=1/(1+2pqpq)  
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.