TIFR PHD CS & SS 2019
Question 1 
Let X be a set with n elements. How many subsets of X have odd cardinality?
n  
2^{n}  
2^{n/2}  
2^{n1}  
Cannot be determined without knowing whether n is odd or even 
Question 2 
How many proper divisors (that is, divisors other than 1 or 7200) does 7200 have?
18  
20  
52  
54  
60 
Question 3 
A is an nXn square matrix for which the entries in every row sum to 1. Consider the following statements:
(i) The column vector [1, 1, . . . , 1]^{T} is an eigenvector of A.
(ii) det(A − I) = 0.
(iii) det(A) = 0.
Which of the above statements must be TRUE?
(i) The column vector [1, 1, . . . , 1]^{T} is an eigenvector of A.
(ii) det(A − I) = 0.
(iii) det(A) = 0.
Which of the above statements must be TRUE?
Only (i)  
Only (ii)  
Only (i) and (ii)  
Only (i) and (iii)  
(i), (ii) and (iii) 
Question 4 
What is the probability that a point P=(α,β) picked uniformly at random from the disk x^{2} + y^{2} ≤ 1 satisfies α + β ≤ 1?
1/π
 
(3/4)+(1/4).(1/π)  
(3/4)+(1/4).(2/π)  
1  
2/π 
Question 5 
Asha and Lata play a game in which Lata first thinks of a natural number between 1 and 1000. Asha must find out that number by asking Lata questions, but Lata can only reply by saying “yes” or “no”. Assume that Lata always tells the truth. What is the least number of questions that Asha needs to ask within which she can always find out the number Lata has thought of?
10  
32  
100  
999  
None of the above 
Question 6 
A function f : R → R is said to be convex if for all x, y ∈ R and λ such that 0 ≤ λ ≤ 1,
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y).
Let f : R → R be a convex function, and define the following functions:
p(x) = f (−x), q(x) = −f (−x), and r(x) = f (1 − x).
Which of the functions p, q and r must be convex?
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y).
Let f : R → R be a convex function, and define the following functions:
p(x) = f (−x), q(x) = −f (−x), and r(x) = f (1 − x).
Which of the functions p, q and r must be convex?
Only p  
Only q  
Only r  
Only p and r  
Only q and r 
Question 7 
What are the last two digits of 1! + 2! + . . . + 100!?
00  
13  
30  
33  
73 
Question 8 
Consider the following toy model of traffic on a straight, single lane, highway. We think of cars as points, which move at the maximum speed v that satisfies the fol lowing constraints:
1. The speed is no more than the speed limit v_{max} mandated for the highway.
2. The speed is such that when travelling at this speed, it takes at least time t0 (where t0 is a fixed time representing the reaction time of drivers) to reach the car ahead, in case the car ahead stops suddenly.
Let as assume that in the steady state, all cars on the highway move at the same speed v satisfying both the above constraints, and the distance between any two successive cars is the same. Let ρ denote the “density”, that is, the number of cars per unit length of the highway. Which of the following graphs most accurately captures the relationship between the speed v and density ρ in this model?
1. The speed is no more than the speed limit v_{max} mandated for the highway.
2. The speed is such that when travelling at this speed, it takes at least time t0 (where t0 is a fixed time representing the reaction time of drivers) to reach the car ahead, in case the car ahead stops suddenly.
Let as assume that in the steady state, all cars on the highway move at the same speed v satisfying both the above constraints, and the distance between any two successive cars is the same. Let ρ denote the “density”, that is, the number of cars per unit length of the highway. Which of the following graphs most accurately captures the relationship between the speed v and density ρ in this model?
a  
b  
c  
d  
e 
Question 9 
Let A and B be two containers. Container A contains 50 litres of liquid X and container B contains 100 litres of liquid Y . Liquids X and Y are soluble in each other.
We now take 30ml of liquid X from container A and put it into container B. The mixture in container B is then thoroughly mixed and 20ml of the resulting mixture is put back into container A. At the end of this process let V_{AY} be the volume of liquid Y in container A and V_{BX} be the volume of liquid X in container B. Which of the following must be TRUE?
V_{AY} < V_{BX}  
V_{AY} > V_{BX}  
V_{AY} = V_{BX}  
V_{AY} + V_{BX} = 30  
V_{AY} + V_{BX} = 20 
Question 10 
Avni and Badal alternately choose numbers from the set {1, 2, 3, 4, 5, 6, 7, 8, 9} without replacement (starting with Avni). The first person to choose numbers of which any 3 sum to 15 wins the game (for example, Avni wins if she chooses the numbers 8, 3, 5, 2, since 8 + 5 + 2 = 15). A player is said to have a winning strategy if the player can always win the game, no matter what the other player does. Which of the following statements is TRUE?
As a hint, there are exactly 8 ways in which 3 numbers from the set {1, 2, 3, 4, 5, 6, 7, 8, 9} can sum up to 15, shown as the three rows, the three columns, and the two diagonals in the following square:
8 1 6
3 5 7
4 9 2
As a hint, there are exactly 8 ways in which 3 numbers from the set {1, 2, 3, 4, 5, 6, 7, 8, 9} can sum up to 15, shown as the three rows, the three columns, and the two diagonals in the following square:
8 1 6
3 5 7
4 9 2
Avni has a winning strategy  
Badal has a winning strategy  
Both of them have a winning strategy  
Neither of them has a winning strategy  
The player that picks 9 has a winning strategy 
Question 11 
Suppose there are n guests at a party (and no hosts). As the night progresses, the guests meet each other and shake hands. The same pair of guests might shake hands multiple times, for some parties stretch late into the night, and it is hard to keep track. Still, they don’t shake hands with themselves. Let Odd be the set of guests who have shaken an odd number of hands, and let Even be the set of guests who have shaken an even number of hands. Which of the following stays invariant throughout the night?
Odd mod 2  
Even  
Even • Odd  
2Even − Odd  
2Odd − Even 
Question 12 
Let f be a function with both input and output in the set {0, 1, 2, . . . , 9}, and let the function g be defined as g(x) = f (9 − x). The function f is nondecreasing, so that f (x) ≥ f (y) for x ≥ y. Consider the following statements:
(i) There exists x ∈ {0, . . . , 9} so that x = f (x).
(ii) There exists x ∈ {0, . . . , 9} so that x = g(x).
(iii) There exists x ∈ {0, . . . , 9} so that x = (f (x) + g(x)) mod 10.
Which of the above statements must be TRUE for ALL such functions f and g?
(i) There exists x ∈ {0, . . . , 9} so that x = f (x).
(ii) There exists x ∈ {0, . . . , 9} so that x = g(x).
(iii) There exists x ∈ {0, . . . , 9} so that x = (f (x) + g(x)) mod 10.
Which of the above statements must be TRUE for ALL such functions f and g?
Only (i)  
Only (i) and (ii)  
Only (iii)  
None of them  
All of them 
Question 14 
A drawer contains 9 pens, of which 3 are red, 3 are blue, and 3 are green. The nine pens are drawn from the drawer one at a time (without replacement) such that each pen is drawn with equal probability from the remaining pens in the drawer. What is the probability that two red pens are drawn in succession?
7/12  
1/6  
1/12  
1/81  
None of the above 
Question 15 
a  
b  
c  
0 1/2 1/2 0 1/2 1/2 0 1/2 1/2  
The limit exists, but it is none of the above 
Question 16 
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits?
0.1  
0.2  
0.4  
0.5  
All the above 
Question 17 
How many distinct minimum weight spanning trees does the following undirected, weighted graph have?
8  
16  
32  
64  
None of the above 
Question 18 
A graph is dregular if every vertex has degree d. For a dregular graph on n vertices, which of the following must be TRUE?
d divides n  
Both d and n are even  
Both d and n are odd  
At least one of d and n is odd  
At least one of d and n is even 
Question 20 
Stirling’s approximation for n! states that for some constants c1, c2,
a  
b  
c  
n! = Θ((n/e)^{n+(1/2)})  
n! = (n^{n+(1/2)}2^{n}) 
Question 21 
Given the following pseudocode for function printx() below, how many times is x printed if we execute printx(5)?
void printx(int n) { if (n==0) {
printf("x");
}
for (int i=0;i<=n1;++i){ printx(n1);
}
}
void printx(int n) { if (n==0) {
printf("x");
}
for (int i=0;i<=n1;++i){ printx(n1);
}
}
625  
256  
120  
24  
5 
Question 22 
A formula is said to be a 3CFformula if it is a conjunction (i.e., an AND) of clauses, and each clause has at most 3 literals. Analogously, a formula is said to be a 3DF formula if it is a disjunction (i.e., an OR) of clauses of at most 3 literals each.
Define the languages 3CFSAT and 3DFSAT as follows:
3CFSAT = {Φ  Φ is a satisfiable 3CF formula}
3DFSAT = {Φ  Φ is a satisfiable 3DF formula}
Which of the following best represents our current knowledge of these languages?
Define the languages 3CFSAT and 3DFSAT as follows:
3CFSAT = {Φ  Φ is a satisfiable 3CF formula}
3DFSAT = {Φ  Φ is a satisfiable 3DF formula}
Which of the following best represents our current knowledge of these languages?
Both 3CFSAT and 3DFSAT are in NP but only 3CFSAT is NP complete  
Both 3CFSAT and 3DFSAT are NPcomplete  
Both 3CFSAT and 3DFSAT are in P  
Both 3CFSAT and 3DFSAT are in NP but only 3DFSAT is NPcomplete  
Neither 3CFSAT nor 3DFSAT are in P 
Question 23 
Consider the following program fragment:
var a, b : integer ;
procedure G (c, d : integer) ; begin
c := c  d ; d := c + d ; c := d  c
end ;
a := 2 ;
b := 3 ; G (a, b);
If both parameters to G are passed by reference, what are the values of a and b at the end of the above program fragment?
var a, b : integer ;
procedure G (c, d : integer) ; begin
c := c  d ; d := c + d ; c := d  c
end ;
a := 2 ;
b := 3 ; G (a, b);
If both parameters to G are passed by reference, what are the values of a and b at the end of the above program fragment?
a = 0 and b = 2  
a = 3 and b = 2  
a = 2 and b = 3  
a = 1 and b = 5  
None of the above 
Question 24 
Consider the following program fragment:
var x, y: integer ; x := 1; y := 0 ;
while y < x do
begin
x := 2 * x ;
y := y + 1
end ;
For the above fragment, which of the following is a loop invariant?
var x, y: integer ; x := 1; y := 0 ;
while y < x do
begin
x := 2 * x ;
y := y + 1
end ;
For the above fragment, which of the following is a loop invariant?
x = y + 1  
x = (y + 1)^{2}  
x = (y + 1)2^{y}  
x = 2^{y}  
None of the above, since the loop does not terminate 
Question 25 
Let the language D be defined on the binary alphabet {0, 1} as follows:
D := {w ∈ {0, 1}^{∗}  substrings 01 and 10 occur an equal number of times in w}.
For example, 101 ϵ D while 1010 (ϵ)' D. Which of the following must be TRUE of the language D?
D := {w ∈ {0, 1}^{∗}  substrings 01 and 10 occur an equal number of times in w}.
For example, 101 ϵ D while 1010 (ϵ)' D. Which of the following must be TRUE of the language D?
D is regular  
D is contextfree but not regular  
D is decidable but not contextfree  
D is decidable but not in NP  
D is undecidable 
Question 26 
Consider the following nondeterministic automaton, where s1 is the start state and s4 is the final (accepting) state. The alphabet is a, b . A transition with label s can be taken without consuming any symbol from the input.
https://solutionsadda.in/wpcontent/uploads/2020/04/tifr7.jpg
Which of the following regular expressions corresponds to the language accepted by this automaton?
https://solutionsadda.in/wpcontent/uploads/2020/04/tifr7.jpg
Which of the following regular expressions corresponds to the language accepted by this automaton?
(a + b)^{∗}aba  
(a + b)^{∗}ba^{∗}  
(a + b)^{∗}ba(aa)^{∗}  
(a + b)^{∗}  
(a + b)^{∗}baa^{∗} 
Question 27 
Let G = (V, E) be a directed graph with n ( >= 2) vertices, including a special vertex r. Each edge e ∈ E has a strictly positive edge weight w(e).
An arborescence in G rooted at r is a subgraph H of G in which every vertex u ∈ V \ { r } has a directed path to the special vertex r.
The weight of an arborescence H is the sum of the weights of the edges in H.
Let H^{∗} be a minimum weight arborescence rooted at r, and w^{∗} the weight of H^{∗}. Which of the following is NOT always true?
An arborescence in G rooted at r is a subgraph H of G in which every vertex u ∈ V \ { r } has a directed path to the special vertex r.
The weight of an arborescence H is the sum of the weights of the edges in H.
Let H^{∗} be a minimum weight arborescence rooted at r, and w^{∗} the weight of H^{∗}. Which of the following is NOT always true?
H^{∗} has exactly n − 1 edges  
H^{∗} is acyclic  
w^{∗} is less than the weight of the minimum weight directed Hamiltonian cycle in
G, whenever G has a directed Hamiltonian cycle

Question 28 
A row of 10 houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a red or a blue house must be green. How many ways are there to paint the houses?
199  
683  
1365  
3^{10} − 2^{10}  
3^{10} 
Question 29 
Let m and n be two positive integers. Which of the following is NOT always true?
If m and n are coprime, there exist integers a and b such that am + bn = 1  
m^{n−1} ≡ 1 (mod n)  
m + 1 is a factor of m^{n(n+1)} − 1  
If 2^{n} − 1 is prime, then n is prime 
Question 30 
Consider directed graphs on n labelled vertices { 1, 2, . . . , n } where each vertex has exactly one edge coming in and exactly one edge going out. We allow selfloops. How many such graphs have exactly two cycles?
a  
b  
c  
d  
None of the above 
Question 31 
Only α = β = γ = 0  
Only α = β = 0 (parameter γ can take any value)  
Only α = 0 (parameters β and γ can take arbitrary values)
 
Always nonlinear, but timeinvariant only if α = 0 (parameters β and γ can take arbitrary values)  
Cannot be determined from the information given 
Question 32 
Let A and B be two square matrices that have full rank. Let λ_{A} be an eigenvalue of A and λ_{B} an eigenvalue of B. Which of the following is always TRUE?
AB has full rank  
A − B has full rank  
λ_{A}λ_{B} is an eigenvalue of AB  
A + B has full rank  
At least one of λ_{A} or λ_{B} is an eigenvalue of AB 
Question 33 
Consider a function f : R > R such that f (x) = 1 if x is rational, and f (x) = 1∈, where 0 < ∈ < 1, if x is irrational. Which of the following is TRUE?
lim_{x→∞} f (x) = 1  
lim_{x→∞} f (x) = 1 − ∈  
lim_{x→∞} f (x) exists, but is neither 1 nor 1 − ∈  
max_{x≥1} f (x) = 1  
None of the above 
Question 34 
Let f (x) = √(x^{2}4x + 4), for x ∈ (∞, ∞) Here, √y denotes the nonnegative square root of y when y is nonnegative. Then, which of the following is TRUE?
f(x) is not continuous but differentiable  
f(x) is continuous and differentiable  
f(x) is continuous but not differentiable  
f(x) is neither continuous nor differentiable  
None of the above 
Question 35 
Consider the function f(x) = e^{x2}  8x^{2} for all x on the real line. For how many distinct values of x do we have f(x)=0?
1  
4  
2  
3  
5 
Question 36 
Suppose that X_{1} and X_{2} denote the random outcomes of independent rolls of two dice. Each of the dice takes each of the six values 1, 2, 3, 4, 5, and 6 with equal probability. What is the value of the conditional expectation
E[max(X1, X2) min(X_{1}, X_{2}) = 3]?
E[max(X1, X2) min(X_{1}, X_{2}) = 3]?
33/7  
4  
5  
9/2  
19/4 
Question 38 
a  
b  
c  
d  
e 
Question 39 
Consider a coin which comes up heads with probability p and tails with probability 1p, where 0 < p < 1. Suppose we keep tossing the coin until we have seen both sides of the coin. What is the expected number of times we would have seen tails? (Hint: the expected number of tosses required to see heads for the first time is 1/p.)
1/p  
1+ (1/(1p))  
p+(1/p)1  
2  
None of the above 
Question 40 
max(p1, p2)  
min(p1, p2)  
1/p1 + 1/p2)−1  
(1 + 1/p1 + 1/p2)−1  
None of the above 
Question 41 
Let X and Y be independent Gaussian random variables with means 1 and 2 and variances 3 and 4 respectively. What is the minimum possible value of E [(X + Y t)^{2}], when t varies over all real numbers?
7  
5  
1.5  
3.5  
2.5 
Question 42 
Consider an urn with a red and b blue balls. Balls are drawn out onebyone, without replacement and uniformly at random, until the first red ball is drawn. What is the expected total number of balls drawn by this process? (Hint: Consider deriving an appropriate recurrence.)
(a+b)/(a+1)  
(a+b+1)/a  
(a+b)a  
(a+b+1)/a+1  
a 
Question 44 
Consider the circle of radius 1 centred at the origin in two dimensions. Choose two points x and y independently at random so that both are uniformly distributed on the circle. Let the vectors joining the origin to x and y be X and Y, respectively. Let θ be the angle between X and Y, measured in an anticlockwise direction while moving along the circle from x towards y. Which of the following is TRUE?
E[θ] = π  
E[x−y^{2}] = √2  
E [x − y^{2}] = 1 + √2  
Ex − y^{2}] = √3  
E[x − y^{2}] = 1 
Question 45 
Anu reached a bus stop at 9:00 AM. She knows that the number of minutes after 9:00 AM when the bus will arrive is distributed with probability density function (p.d.f.) f where
f(x)=(1/10)*exp(−x/10)
for x ≥ 0, and f (x) = 0 for x < 0.
At 9:05 AM, the bus had still not arrived. Given her knowledge of this fact and of the p.d.f. f of the arrival time of the bus, at what time, measured in minutes after 9:00 AM, would Anu expect the bus to arrive?
f(x)=(1/10)*exp(−x/10)
for x ≥ 0, and f (x) = 0 for x < 0.
At 9:05 AM, the bus had still not arrived. Given her knowledge of this fact and of the p.d.f. f of the arrival time of the bus, at what time, measured in minutes after 9:00 AM, would Anu expect the bus to arrive?
12.5  
15  
7.5  
10  
12.5 
There are 45 questions to complete.