TIFR PHD CS & SS 2016
Question 1 
Suppose the following statements about three persons in a room are true.
"Chandni, Sooraj and Tara are in a room. nobody else is in the room.
Chandni is looking at Sooraj. Sooraj is looking at Tara.
Chandni is married. Tara is not married.
A married person in the room is looking at an unmarried person."
Then, which of the following is necessarily true?
"Chandni, Sooraj and Tara are in a room. nobody else is in the room.
Chandni is looking at Sooraj. Sooraj is looking at Tara.
Chandni is married. Tara is not married.
A married person in the room is looking at an unmarried person."
Then, which of the following is necessarily true?
Sooraj is married  
Sooraj is unmarried  
The situation described is impossible  
There is insufficient information to conclude if Sooraj is married or unmarried  
None of the above 
Question 3 
S is empty  
S is a subspace of R^{3n} of dimension 1  
S is a subspace of R^{3n} of dimension n  
S is a subspace of R^{3n} of dimension n − 1  
S has exactly n elements 
Question 6 
Which of the following statements about the eigen values of In, the nXn identity matrix (over complex numbers), is true?
The eigen values are 1, ω, ω^{2}, . . . , ω^{n−1}, where ω is a primitive nth root of unity  
The only eigen value is −1  
Both 0 and 1 are eigen values, but there are no other eigen values  
The eigen values are 1, 1/2, 1/3, . . . , 1/n  
The only eigen value is 1 
Question 7 
Let S be the 4X4 square grid {(x, y) : x, y ε { 0, 1, 2, 3 }}. A monotone path in this grid starts at (0, 0) and at each step either moves one unit up or one unit right. For example, from the point (x, y) one can in one step either move to (x + 1, y) ε S or (x, y + 1) ε S, but never leave S. Let the number of distinct monotone paths to reach point (2, 2) starting from (0, 0) be z. How many distinct monotone paths are there to reach point (3, 3) starting from (0, 0)?
2Z+6  
3Z+6  
2Z+8  
3Z+8  
3Z+4 
Question 8 
Always 0  
Always 1  
0 if A = B and 1 otherwise.  
1 if A = B and 0 otherwise  
Depends on the size of the universe 
Question 9 
Suppose a rectangular farm has area 100 square metres. The lengths of its sides are not known. It is known, however, that all the edges are at least 2 metres in length. Which of the following statements about the rectangle’s perimeter p (in metres) is FALSE?
p can take all values between 45 and 50  
p can be 52 for some configuration  
p can take all values between 55 and 60  
p can be 70 for some configuration  
p can be 39 for some configuration 
Question 10 
Consider the sequence (s_{n} : n ≥ 0) defined as follows: s_{0} = 0, s_{1} = 1, s_{2} = 1, and s_{n} = s_{n1} + s_{n2} + s_{n3}, for n ≥ 3. Which of the following statements is FALSE?
s_{4k} is even, for any k ≥ 0  
s_{4k+1} is odd, for any k ≥ 0  
s_{4k+2} is odd, for any k ≥ 0  
s_{n} is a multiple of 3, for only finitely many values of n  
s_{4k+3} is even, for any k ≥ 0 
Question 11 
In one of the islands that his travels took him to, Gulliver noticed that the probability that a (uniformly) randomly chosen inhabitant has height at least 2 metres is 0.2. Also, 0.2 is the probability that a (uniformly) randomly chosen inhabitant has height at most 1.5 metres. What can we conclude about the average height h in metres of the inhabitants of the island?
(i) 1.5 ≤ h ≤ 2
(ii) h ≥ 1.3
(iii) h ≤ 2.2
Which of the above statements is necessarily true?
(i) 1.5 ≤ h ≤ 2
(ii) h ≥ 1.3
(iii) h ≤ 2.2
Which of the above statements is necessarily true?
(ii) only  
(iii) only  
(i), (ii), and (iii)  
(ii) and (iii) only  
None of the above 
Question 12 
There are two rocks A and B, located close to each other, in a lily pond. There is a frog that jumps randomly between the two rocks at time t = 0, 1, 2, The location
of the frog is determined as follows. Initially, at time t = 0, the frog is at A. From then on, the frog’s location is determined as follows. If the frog is at A at time t, then at time t + 1, with probability 2/3 it jumps to B and with probability 1/3, it jumps on the spot and stays at A. If the frog is at B at time t, then at time t + 1, with probability 1/2 it jumps to A and with probability 1/2 it jumps on the spot and stays at B. What is the probability that the frog is at B at time 3 (just after its third jump)?
1/2  
31/54  
14/27  
61/108  
2/3 
Question 13 
Let n ≥ 2 be any integer. Which of the following statements is not necessarily true?
a  
b  
c  
d  
e 
Question 14 
A diagonal in a polygon is a straight line segment that connects two nonadjacent vertices, and is contained in the interior of the polygon (except for its end points). Two such diagonals are said to cross if they have a point in common in the interior of the polygon. In one such polygon with n vertices, a certain number (say k) of noncrossing diagonals were drawn to cut up the inside of the polygon into regions, each of which was a quadrilateral. How many diagonals were drawn, that is, what is k?
Cannot be determined from the information given  
n − 2  
n − 1  
n − 4  
n^{2} − 9.5n + 22 
Question 15 
In a tournament with 7 teams, each team plays one match with every other team. For each match, the team earns two points if it wins, one point if it ties, and no points if it loses. At the end of all matches, the teams are ordered in the descending order of their total points (the order among the teams with the same total are determined by a whimsical tournament referee). The first three teams in this ordering are then chosen to play in the next round. What is the minimum total number of points a team must earn in order to be guaranteed a place in the next round?
13  
12  
11  
10  
9 
Question 16 
A Boolean formula is said to be a tautology if it evaluates to TRUE for all assignments to its variables. Which one of the following is NOT a tautology?
((p ∨ q) ∧ (r ∨ s)) ⇒ ((p ∧ r) ∨ q ∨ s)  
((p ∨ q) ∧ (r ∨ s)) ⇒ (q ∨ s)  
((p ∨ q) ∧ (r ∨ s)) ⇒ (r ∨ q ∨ s)  
((p ∨ q) ∧ (r ∨ s)) ⇒ (p ∨ q ∨ s)  
((p ∨ q) ∧ (r ∨ s)) ⇒ (p ∨ q) 
Question 17 
Which language class has the following properties?
It is closed under union and intersection but not complement.
It is closed under union and intersection but not complement.
Regular language  
Contextfree languages  
Recursive languages  
Recursively enumerable languages  
Languages that are not recursively enumerable 
Question 18 
Assume P ≠ NP . Which of the following is not TRUE?
2SAT is in NP  
2SAT is in coNP  
3SAT is polyonomialtime reducible to 2SAT  
4SAT is polynomialtime reducible to 3SAT  
2SAT is in P 
Question 20 
Consider the following recursive function mc91.
int mc91(int n)
{
print n
if (n > 100) { return n  10;
}
else {
return mc91(mc91(n+11));
}
}
Let
Out = {n : there is an x ∈ {0, 1, . . . , 100} such that n is one of the integers printed by mc91(x)}.
Then, which of the following is Out?
int mc91(int n)
{
print n
if (n > 100) { return n  10;
}
else {
return mc91(mc91(n+11));
}
}
Let
Out = {n : there is an x ∈ {0, 1, . . . , 100} such that n is one of the integers printed by mc91(x)}.
Then, which of the following is Out?
{n : −∞ < n ≤ 100}  
{n : 0 ≤ n ≤ 101}  
{n : 0 ≤ n ≤ 110}  
{n : 0 ≤ n ≤ 111}  
{n : 0 ≤ n < +∞} 
Question 21 
a  
b  
c  
d  
e 
Question 22 
Let n = m!. Which of the following is TRUE?
m = Θ(log n/ log log n)  
m = Ω(log n/ log log n) but not m = O(log n/ log log n)  
m = Θ(log^{2} n)  
m = Ω(log^{2} n) but not m = O(log^{2} n)  
m = Θ(log^{1.5} n) 
Question 23 
PRIMES is regular  
PRIMES is undecidable  
PRIMES is decidable in polynomial time  
PRIMES context free but not regular  
PRIMES is NPcomplete and P ≠ NP 
Question 24 
Which of the following graphs DOES NOT have an Eulerian circuit? (Recall that an Eulerian circuit in an undirected graph is a walk in the graph that starts at a vertex and returns to the vertex after travelling on each edge exactly once.)
K_{9,9}  
K_{8,8}  
K_{12,12}  
K_{9}  
The graph G on vertex set {1, 2, . . . , 9} with edge set E(G) = {{i, j} : 1 ≤ i < j ≤ 5 or 5 ≤ i < j ≤ 9}. 
Question 25 
A vertex cover in an undirected graph G is a subset C ⊆ V (G) such that every edge of G has an endpoint in C. An independent set in G is a subset I ⊆ V (G) such that no edge has both its endpoints in I. Which of the following is TRUE of every graph G and every vertex cover C of G?
There exists an independent set of size C  
V (G) − C is an independent set  
C ≥ E(G)/2  
C ≥ V (G)/2  
C intersects every independent set 
Question 26 
H has an infinite number of vertices  
The diameter of H is infinite  
H is connected  
H contains an infinite clique  
H contains an infinite independent set 
Question 27 
a  
b  
c  
d  
e 
Question 28 
An undirected graph G = (V, E) is said to be kcolourable if there exists a mapping c : V >{1, 2, . . . , k} such that for every edge {u, v}ϵE we have c(u) ≠ c(v). Which of the following statements is FALSE?
G is V colourable  
G is 2colourable iff there are no odd cycles in G  
G is (∆ + 1)colourable where ∆ is the maximum degree in G  
There is a polynomial time algorithm to check if G is 2colourable  
If G has no triangle then it is 3colourable

Question 29 
F ≤ 2n and there exists a family F such that F = 2n  
F ≤ n2 and there exists a family F such that F = n^{2}  
F ≤ 2n2 and there exists a family F such that F = 2n^{2}  
F ≤ 2n−1 and there exists a family F such that F = 2^{n−1}  
None of the above 
Question 30 
Let G be an undirected graph. For a pair (x, y) of distinct vertices of G, let mincut(x, y) be the least number of edges that should be deleted from G so that the resulting graph has no xy path. Let a, b, c be three vertices in G such that mincut(a, b) ≤ mincut(b, c) ≤ mincut(c, a). Consider the following possibilities:
(i) mincut(a, b) < mincut(b, c) < mincut(c, a)
(ii) mincut(a, b) = mincut(b, c) < mincut(c, a)
(iii) mincut(a, b) < mincut(b, c) = mincut(c, a)
(iv) mincut(a, b) = mincut(b, c) = mincut(c, a) Which of the following is TRUE?
All of (i), (ii), (iii), (iv) are possible  
(i), (ii), (iii) are possible but not (iv)  
(i) and (iv) are possible but neither (ii) nor (iii)  
(ii) and (iv) are possible but neither (i) nor (iii)  
(iii) and (iv) are possible but neither (i) nor (ii) 
Question 33 
Let (X, Y ) be a pair of independent random variables. Suppose X takes values in {1, . . . , 6} with equal probability, and Y takes values in {2, 3} with Pr[Y = 2] = p. Let Z = (X mod Y ) + 1.
Which of the statements is true?
Which of the statements is true?
a  
b  
c  
d  
e 
Question 34 
Consider a system which in response to input x(t) outputs
y(t) = x(t^{2}).
Which of the following describes the system?
y(t) = x(t^{2}).
Which of the following describes the system?
linear, timeinvariant, causal  
linear, timeinvariant, noncausal  
linear, timevariant  
nonlinear, timeinvariant  
nonlinear, timevariant 
Question 35 
a  
b  
c  
d  
e 
Question 37 
a  
v  
c  
d  
e 
Question 38 
a  
b  
c  
d  
All four circuits are equivalent 
Question 40 
Let U1, U2, U3 be independent random variables that are each uniformly distributed between zero and one. What is the probability that the second highest value amongst the three lies between 1/3 and 2/3?
2/9  
1/27  
13/27  
1/3  
7/18 
Question 41 
Suppose that a random variable X has a probability density function (pdf) given by
f (x) = c exp(−2x)
for x ≥ 1, and f (x) = 0, for x < 1, where c is an appropriate constant so that f (x) is a valid pdf.
What is the expected value of X given that X ≥ 5?
f (x) = c exp(−2x)
for x ≥ 1, and f (x) = 0, for x < 1, where c is an appropriate constant so that f (x) is a valid pdf.
What is the expected value of X given that X ≥ 5?
5*(1/2)  
7  
10  
8*(1/2)  
6 
Question 42 
log_{2}513  
9  
10  
19  
81 
Question 43 
Suppose m and n are positive integers, m ≠ n, and A is an m X n matrix with real entries. Consider the following statements.
(i) rank(AA^{T} ) = rank(A^{T} A)
(ii) det(A^{T} A) = det(AA^{T} )
(iii) Trace(AA^{T} ) = Trace(A^{T} A)
Which of the above statements is true for all such A?
(i) rank(AA^{T} ) = rank(A^{T} A)
(ii) det(A^{T} A) = det(AA^{T} )
(iii) Trace(AA^{T} ) = Trace(A^{T} A)
Which of the above statements is true for all such A?
Only (i)  
Only (ii)  
Only (iii)  
(i) and (iii)  
None of them 
There are 45 questions to complete.