## TIFR PHD CS & SS 2019

 Question 1
Let X be a set with n elements. How many subsets of X have odd cardinality?
 A n B 2n C 2n/2 D 2n-1 E Cannot be determined without knowing whether n is odd or even
Engineering-Mathematics       Set-Theory
 Question 2
How many proper divisors (that is, divisors other than 1 or 7200) does 7200 have?
 A 18 B 20 C 52 D 54 E 60
Engineering-Mathematics       Combinatorics
 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?
 A Only (i) B Only (ii) C Only (i) and (ii) D Only (i) and (iii) E (i), (ii) and (iii)
Engineering-Mathematics       Linear-Algebra
 Question 4
What is the probability that a point P=(α,β) picked uniformly at random from the disk x2 + y2 ≤ 1 satisfies α + β ≤ 1?
 A 1/π B (3/4)+(1/4).(1/π) C (3/4)+(1/4).(2/π) D 1 E 2/π
Engineering-Mathematics       Probability-and-statistics
 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?
 A 10 B 32 C 100 D 999 E None of the above
Engineering-Mathematics       Combinatorics
 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?
 A Only p B Only q C Only r D Only p and r E Only q and r
Engineering-Mathematics       Relations-and-Functions
 Question 7
What are the last two digits of 1! + 2! + . . . + 100!?
 A 00 B 13 C 30 D 33 E 73
Engineering-Mathematics       Combinatorics
 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 vmax 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 a B b C c D d E 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 VAY be the volume of liquid Y in container A and VBX be the volume of liquid X in container B. Which of the following must be TRUE?
 A VAY < VBX B VAY > VBX C VAY = VBX D VAY + VBX = 30 E VAY + VBX = 20
Aptitude       Numerical
 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
 A Avni has a winning strategy B Badal has a winning strategy C Both of them have a winning strategy D Neither of them has a winning strategy E The player that picks 9 has a winning strategy
Aptitude       Numerical
 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?
 A |Odd| mod 2 B |Even| C |Even| • |Odd| D 2|Even| − |Odd| E 2|Odd| − |Even|
Aptitude       Numerical
 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?
 A Only (i) B Only (i) and (ii) C Only (iii) D None of them E All of them
Engineering-Mathematics       Relations-and-Functions
 Question 13 A 0 B 0.02 C 0.1 D 0.33 E 1
Engineering-Mathematics       Calculus
 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?
 A 7/12 B 1/6 C 1/12 D 1/81 E None of the above
Engineering-Mathematics       Probability-and-statistics
 Question 15 A a B b C c D 0 1/2 1/2 0 1/2 1/2 0 1/2 1/2 E The limit exists, but it is none of the above
Engineering-Mathematics       Linear-Algebra
 Question 16
Which of the following decimal numbers can be exactly represented in binary notation with a finite number of bits?
 A 0.1 B 0.2 C 0.4 D 0.5 E All the above
Digital-Logic-Design       Number-Systems
 Question 17
How many distinct minimum weight spanning trees does the following undirected, weighted graph have? A 8 B 16 C 32 D 64 E None of the above
Algorithms       Minimum-Spanning-Tree
 Question 18
A graph is d-regular if every vertex has degree d. For a d-regular graph on n vertices, which of the following must be TRUE?
 A d divides n B Both d and n are even C Both d and n are odd D At least one of d and n is odd E At least one of d and n is even
Engineering-Mathematics       Graph-Theory
 Question 19 A q B ϕ itself C q ∨ s D q ∨ r E ¬q ∧ s
Engineering-Mathematics       Propositional-Logic
 Question 20
Stirling’s approximation for n! states that for some constants c1, c2, A a B b C c D n! = Θ((n/e)n+(1/2)) E n! = (nn+(1/2)2-n)
Algorithms       Asymptotic-Complexity
 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<=n-1;++i){ printx(n-1);
}
}
 A 625 B 256 C 120 D 24 E 5
Programming       Functions
 Question 22
A formula is said to be a 3-CF-formula 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 3-DF- formula if it is a disjunction (i.e., an OR) of clauses of at most 3 literals each.
Define the languages 3-CF-SAT and 3-DF-SAT as follows:
3-CF-SAT = {Φ | Φ is a satisfiable 3-CF formula}
3-DF-SAT = {Φ | Φ is a satisfiable 3-DF formula}
Which of the following best represents our current knowledge of these languages?
 A Both 3-CF-SAT and 3-DF-SAT are in NP but only 3-CF-SAT is NP- complete B Both 3-CF-SAT and 3-DF-SAT are NP-complete C Both 3-CF-SAT and 3-DF-SAT are in P D Both 3-CF-SAT and 3-DF-SAT are in NP but only 3-DF-SAT is NP-complete E Neither 3-CF-SAT nor 3-DF-SAT are in P
Algorithms       P-NP
 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?
 A a = 0 and b = 2 B a = 3 and b = 2 C a = 2 and b = 3 D a = 1 and b = 5 E None of the above
Programming       Prameters-passing-mechanisms
 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?
 A x = y + 1 B x = (y + 1)2 C x = (y + 1)2y D x = 2y E None of the above, since the loop does not terminate
Programming       Control-Statement
 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?
 A D is regular B D is context-free but not regular C D is decidable but not context-free D D is decidable but not in NP E D is undecidable
Theory-of-Computation       Languages-and-Grammars
 Question 26
Consider the following non-deterministic 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.
Which of the following regular expressions corresponds to the language accepted by this automaton?
 A (a + b)∗aba B (a + b)∗ba∗ C (a + b)∗ba(aa)∗ D (a + b)∗ E (a + b)∗baa∗
Theory-of-Computation       Regular-Expression
 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?
 A B C H∗ has exactly n − 1 edges D H∗ is acyclic E w∗ is less than the weight of the minimum weight directed Hamiltonian cycle in G, whenever G has a directed Hamiltonian cycle
Engineering-Mathematics       Graph-Theory
 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?
 A 199 B 683 C 1365 D 310 − 210 E 310
Engineering-Mathematics       Combinatorics
 Question 29
Let m and n be two positive integers. Which of the following is NOT always true?
 A If m and n are co-prime, there exist integers a and b such that am + bn = 1 B mn−1 ≡ 1 (mod n) C D m + 1 is a factor of mn(n+1) − 1 E If 2n − 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 self-loops. How many such graphs have exactly two cycles? A a B b C c D d E None of the above
Engineering-Mathematics       Graph-Theory
 Question 31 A Only α = β = γ = 0 B Only α = β = 0 (parameter γ can take any value) C Only α = 0 (parameters β and γ can take arbitrary values) D Always non-linear, but time-invariant only if α = 0 (parameters β and γ can take arbitrary values) E 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?
 A AB has full rank B A − B has full rank C λAλB is an eigenvalue of AB D A + B has full rank E At least one of λA or λB is an eigenvalue of AB
Engineering-Mathematics       Linear-Algebra
 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?
 A limx→∞ f (x) = 1 B limx→∞ f (x) = 1 − ∈ C limx→∞ f (x) exists, but is neither 1 nor 1 − ∈ D maxx≥1 f (x) = 1 E None of the above
Engineering-Mathematics       Calculus
 Question 34
Let f (x) = √(x2-4x + 4), for x ∈ (-∞, ∞) Here, √y denotes the non-negative square root of y when y is non-negative. Then, which of the following is TRUE?
 A f(x) is not continuous but differentiable B f(x) is continuous and differentiable C f(x) is continuous but not differentiable D f(x) is neither continuous nor differentiable E None of the above
Engineering-Mathematics       Calculus
 Question 35
Consider the function f(x) = ex2 - 8x2 for all x on the real line. For how many distinct values of x do we have f(x)=0?
 A 1 B 4 C 2 D 3 E 5
Engineering-Mathematics       Calculus
 Question 36
Suppose that X1 and X2 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(X1, X2) = 3]?
 A 33/7 B 4 C 5 D 9/2 E 19/4
Engineering-Mathematics       Probability-and-statistics
 Question 37 A a B b C c D d E e
Engineering-Mathematics       Probability-and-statistics
 Question 38  A a B b C c D d E e
 Question 39
Consider a coin which comes up heads with probability p and tails with probability 1-p, 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.)
 A 1/p B 1+ (1/(1-p)) C p+(1/p)-1 D 2 E None of the above
Engineering-Mathematics       Probability-and-statistics
 Question 40 A max(p1, p2) B min(p1, p2) C 1/p1 + 1/p2)−1 D (1 + 1/p1 + 1/p2)−1 E None of the above
Engineering-Mathematics       Probability-and-statistics
 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?
 A 7 B 5 C 1.5 D 3.5 E 2.5
Engineering-Mathematics       Probability-and-statistics
 Question 42
Consider an urn with a red and b blue balls. Balls are drawn out one-by-one, 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 (a+b)/(a+1) B (a+b+1)/a C (a+b)a D (a+b+1)/a+1 E a
Engineering-Mathematics       Probability-and-statistics
 Question 43 A a B b C c D d E e
Engineering-Mathematics       Calculus
 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 anti-clockwise direction while moving along the circle from x towards y. Which of the following is TRUE?
 A E[θ] = π B E[|x−y|2] = √2 C E [|x − y|2] = 1 + √2 D E|x − y|2] = √3 E E[|x − y|2] = 1
Engineering-Mathematics Engineering-Mathematics       Probability-and-statistics
 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?
 A 12.5 B 15 C 7.5 D 10 E 12.5
Engineering-Mathematics       Probability-and-statistics
There are 45 questions to complete.