TIFR PHD CS & SS 2014
Question 1 
Consider the reactions
X + 2Y → 3Z
2X + Z → Y.
Let n_{X}, n_{Y} , n_{Z} denote the numbers of molecules of chemicals X, Y , Z in the reaction chamber. Then
which of the following is conserved by both reactions?
X + 2Y → 3Z
2X + Z → Y.
Let n_{X}, n_{Y} , n_{Z} denote the numbers of molecules of chemicals X, Y , Z in the reaction chamber. Then
which of the following is conserved by both reactions?
n_{X} + n_{Y} + n_{Z}  
n_{X} + 7n_{Y} + 5n_{Z}  
2n_{X} + 9n_{Y}  3n_{Z}  
3n_{X}  3n_{Y} + 13n_{Z}  
None of the above 
Question 2 
A body at a temperature of 30 Celsius is immersed into a heat bath at 0 Celsius at time t = 0. The body starts cooling at a rate proportional to the temperature difference. Assuming that the heat bath does not change in temperature throughout the process, calculate the ratio of the time taken for the body to reach 1 Celsius divided by the time taken for the body to reach 5 Celsius.
log 5  
log 29/log 25  
e^{5}  
1 + log_{6} 5  
None of the above 
Question 3 
The Fibonacci sequence is defined as follows: F_{0} = 0, F_{1} = 1, and for all integers n ≥ 2,
F_{n} = F_{n1} + F_{n2}. Then which of the following statements is FALSE?
F_{n} = F_{n1} + F_{n2}. Then which of the following statements is FALSE?
a  
b  
c  
d  
e 
Question 4 
Consider numbers greater than one that satisfy the following properties:
(a) they have no repeated prime factors;
(b) for all primes p ≥ 2, p divides the number if and only if p − 1 divides the number.
The number of such numbers is
(a) they have no repeated prime factors;
(b) for all primes p ≥ 2, p divides the number if and only if p − 1 divides the number.
The number of such numbers is
0  
5  
100  
Infinite  
None of the above 
Question 5 
The rules for the University of Bombay fiveaside cricket competition specify that the members of each team must have birthdays in the same month. What is the minimum number of mathematics students needed to be enrolled in the department to guarantee that they can raise a team of students?
23  
91  
60  
49  
None of the above 
Question 6 
Karan tells truth with probability 1/3 and lies with probability 2/3. Independently, Arjun tells truth with probability 3/4 and lies with probability 1/4. Both watch a cricket match. Arjun tells you that India won, Karan tells you that India lost. What probability will you assign to India’s win?
1/2  
2/3  
3/4  
5/6  
6/7 
Question 7 
Consider a sequence of nonnegative numbers {x_{n} : n = 1, 2,...}. Which of the following statements cannot be true?
a  
b  
c  
d  
e 
Question 8 
All that glitters is gold. No gold is silver.
Claims:
1. No silver glitters.
2. Some gold glitters.
Then, which of the following is TRUE?
Claims:
1. No silver glitters.
2. Some gold glitters.
Then, which of the following is TRUE?
Only claim 1 follows  
Only claim 2 follows  
Either claim 1 or claim 2 follows but not both  
Neither claim 1 nor claim 2 follows  
Both claim 1 and claim 2 follow 
Question 9 
Solve min x^{2} + y^{2}
subject to
x + y ≥ 10,
2x + 3y ≥ 20,
x ≥ 4,
y ≥ 4.
subject to
x + y ≥ 10,
2x + 3y ≥ 20,
x ≥ 4,
y ≥ 4.
32  
50  
52  
100  
None of the above 
Question 10 
A person went out between 4pm and 5pm to chat with her friend and returned between 5pm and 6pm. On her return, she found that the hourhand and the minutehand of her (wellfunctioning) clock had just exchanged their positions with respect to their earlier positions at the time of her leaving. The person must have gone out to chat at
Twenty five minutes past 4pm  
Twenty six and 122/143 minutes past 4pm  
Twenty seven and 1/3 minutes past 4pm.  
Twenty eight minutes past 4pm  
None of the above 
Question 11 
A large community practices birth control in the following peculiar fashion. Each set of parents continues having children until a son is born; then they stop. What is the ratio of boys to girls in the community if, in the absence of birth control, 51% of the babies are born male?
51:49  
1:1  
49:51  
51:98  
98:51 
Question 12 
The above inequality holds under conditions (1) and (2) but not under condition (3).  
The above inequality holds under conditions (2) and (3) but not under condition (1)  
The above inequality holds under conditions (1) and (3) but not under condition (2).  
The above inequality holds under all the three conditions  
The above inequality holds under none of the three conditions 
Question 13 
Let L be a line on the two dimensional plane. L’s intercepts with the X and Y axes are respectively a and b. After rotating the coordinate system (and leaving L untouched), the new intercepts are a and b respectively. Which of the following is TRUE?
a  
b  
c  
d  
e 
Question 14 
Let m and n be any two positive integers. Then, which of the following is FALSE?
m + 1 divides m^{2n} − 1  
For any prime p, m^{p} ≡ m (modp)  
If one of m, n is prime, then there are integers x, y such that mx + ny = 1  
If m  
If 2^{n} − 1 is prime, then n is prime. 
Question 17 
A fair dice (with faces numbered 1,..., 6) is independently rolled repeatedly. Let X denote the number of rolls till an even number is seen and let Y denote the number of rolls till 3 is seen. Evaluate E(Y X = 2).
6*(5/6)  
6  
5*(1/2)  
6*(1/3)  
5*(2/3) 
Question 18 
a  
b  
c  
d  
e 
Question 19 
Consider the following random function of x
F(x)=1+ Ux + Vx^{2} mod 5,
where U and V are independent random variables uniformly distributed over {0, 1, 2, 3, 4}. Which of the
following is FALSE?
F(x)=1+ Ux + Vx^{2} mod 5,
where U and V are independent random variables uniformly distributed over {0, 1, 2, 3, 4}. Which of the
following is FALSE?
F(1) is uniformly distributed over {0, 1, 2, 3, 4}.  
F(1), F(2) are independent random variables and both are uniformly distributed over {0, 1, 2, 3, 4}  
F(1), F(2), F(3) are independent and identically distributed random variables.  
All of the above.  
None of the above 
Question 20 
Consider the equation x^{2} +y^{2} −3z^{2} −3t^{2} = 0.
The total number of integral solutions of this equation in the range of the first 10000 numbers, i.e., 1 ≤ x, y, z, t ≤ 10000, is
The total number of integral solutions of this equation in the range of the first 10000 numbers, i.e., 1 ≤ x, y, z, t ≤ 10000, is
200  
55  
100  
1  
None of the above 
Question 21 
Let T be a rooted binary tree whose vertices are labelled with symbols a, b, c, d, e, f, g, h, i, j, k.
Suppose the inorder (visit left subtree, visit root, visit right subtree) and postorder (visit left subtree, visit right subtree, visit root) traversals of T produce the following sequences.
inorder: a, b, c, d, e, f, g, h, i, j, k
postorder: a, c, b, e, f, h, j, k, i, g, d
How many leaves does the tree have?
Suppose the inorder (visit left subtree, visit root, visit right subtree) and postorder (visit left subtree, visit right subtree, visit root) traversals of T produce the following sequences.
inorder: a, b, c, d, e, f, g, h, i, j, k
postorder: a, c, b, e, f, h, j, k, i, g, d
How many leaves does the tree have?
THREE.  
FOUR.  
FIVE.  
SIX.  
Cannot be determined uniquely from the given information 
Question 22 
Consider the following code.
def brian(n):
count = 0
while ( n != 0 )
n = n & ( n1 )
count = count + 1
return count
Here n is meant to be an unsigned integer. The operator & considers its arguments in binary and computes their bit wise AND. For example, 22 & 15 gives 6, because the binary (say 8bit) representation of 22 is 00010110 and the binary representation of 15 is 00001111, and the bitwise AND of these binary strings is 00000110, which is the binary representation of 6. What does the function brian return?
def brian(n):
count = 0
while ( n != 0 )
n = n & ( n1 )
count = count + 1
return count
Here n is meant to be an unsigned integer. The operator & considers its arguments in binary and computes their bit wise AND. For example, 22 & 15 gives 6, because the binary (say 8bit) representation of 22 is 00010110 and the binary representation of 15 is 00001111, and the bitwise AND of these binary strings is 00000110, which is the binary representation of 6. What does the function brian return?
The highest power of 2 dividing n, but zero if n is zero  
The number obtained by complementing the binary representation of n.  
The number of ones in the binary representation of n.  
The code might go into an infinite loop for some n.  
The result depends on the number of bits used to store unsigned integers 
Question 23 
Consider the following directed graph.
Suppose a depthfirst traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is T, the number of back edges is B and the number of cross edges is C. Then
Suppose a depthfirst traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is T, the number of back edges is B and the number of cross edges is C. Then
B = 1, C = 1, and T = 4.  
B = 0, C = 2, and T = 4.  
B = 2, C = 1, and T = 3.  
B = 1, C = 2, and T = 3  
B = 2, C = 2, and T = 1. 
Question 24 
Consider the following undirected graph with some edge costs missing
Suppose the wavy edges form a Minimum Cost Spanning Tree for G. Then, which of the following inequalities NEED NOT hold?
Suppose the wavy edges form a Minimum Cost Spanning Tree for G. Then, which of the following inequalities NEED NOT hold?
cost(a, b) ≥ 6.  
cost(b, e) ≥ 5  
cost(e, f) ≥ 5.  
cost(a, d) ≥ 4  
cost(b, c) ≥ 4 
Question 25 
Let G = (V,E) be an undirected connected simple (i.e., no parallel edges or selfloops) graph with the weight function w : E → R on its edge set. Let w(e1) < w(e2) < ··· < w(em), where
E = {e1, e2,...,em}. Suppose T is a minimum spanning tree of G.
Which of the following statements is FALSE?
Which of the following statements is FALSE?
The tree T has to contain the edge e1  
The tree T has to contain the edge e2.  
The minimum weight edge incident on each vertex has to be present in T  
T is the unique minimum spanning tree in G.  
If we replace each edge weight wi = w(ei) by its square w^{2}_{i} , then T must still be a minimum spanning tree of this new instance. 
Question 26 
Consider the problem of computing the minimum of a set of n distinct numbers. We choose a permutation uniformly at random (i.e., each of the n! permutations of <1,...,n> is chosen with probability 1/n!) and we inspect the numbers in the order given by this permutation. We maintain a variable MIN that holds the minimum value seen so far. MIN is initialized to ∞ and if we see a value smaller than MIN during our inspection, then MIN is updated. For example, in the inspection given by the following sequence, MIN is updated four times.
5 9 4 2 6 8 0 3 1 7
What is the expected number of times MIN is updated?
5 9 4 2 6 8 0 3 1 7
What is the expected number of times MIN is updated?
O(1)  
H_{n} = ∑^{n}_{i}=1 1/i  
√n  
n/2  
n 
Question 27 
Which of the following statements is TRUE for all sufficiently large n?
a  
b  
c  
d  
e 
Question 28 
Which of these functions grows fastest with n?
e^{n}/n  
e^{n−0.9 log n}  
2^{n}  
(log n)^{n−1}  
None of the above 
Question 29 
Given a set of n distinct numbers, we would like to determine the smallest three numbers in this set using comparisons. Which of the following statements is TRUE?
These three elements can be determined using O(log^{2} n) comparisons  
O(log^{2} n) comparisons do not suffice, however these three elements can be determined using n+O(1)
comparisons.  
n + O(1) comparisons do not suffice, however these three elements can be determined using n + O(log n) comparisons  
n+O(log n) comparisons do not suffice, however these three elements can be determined using O(n)
comparisons.  
None of the above 
Question 30 
Given a set of n distinct numbers, we would like to determine both the smallest and the largest number. Which of the following statements is TRUE?
These two elements can be determined using O(log^{100} n) comparisons  
O(log^{100} n) comparisons do not suffice, however these two elements can be determined using n +
O(log n) comparisons  
n+O(log n) comparisons do not suffice, however these two elements can be determined using 3⌈n/2⌉
comparisons  
3⌈n/2⌉ comparisons do not suffice, however these two elements can be determined using 2(n − 1)
comparisons  
None of the above. 
Question 31 
Consider the following recurrence relation:
Which of the following statements is FALSE?
Which of the following statements is FALSE?
T(n) is O(n^{3/2}) when k = 3  
T(n) is O(n log n) when k = 3  
T(n) is O(n log n) when k = 4  
T(n) is O(n log n) when k = 5.  
T(n) is O(n) when k = 5. 
Question 32 
Consider the following three statements:
i) Intersection of infinitely many regular languages must be regular.
ii) Every subset of a regular language is regular.
iii) If L is regular and M is not regular then L · M is necessarily not regular.
Which of the following gives the correct true/false evaluation of the above?
i) Intersection of infinitely many regular languages must be regular.
ii) Every subset of a regular language is regular.
iii) If L is regular and M is not regular then L · M is necessarily not regular.
Which of the following gives the correct true/false evaluation of the above?
true, false, true  
false, false, true  
true, false, true  
false, false, false  
true, true, true 
Question 33 
Let L be a given contextfree language over the alphabet {a, b}. Construct L1, L2 as follows.
Let L1 = L − {xyx  x, y ∈ {a, b}^{∗}}, and L2 = L · L. Then
Let L1 = L − {xyx  x, y ∈ {a, b}^{∗}}, and L2 = L · L. Then
Both L1 and L2 are regular  
Both L1 and L2 are context free but not necessarily regular  
L1 is regular and L2 is context free.  
L1 and L2 both may not be context free  
L1 is regular but L2 may not be context free 
Question 34 
Which the following is FALSE?
Complement of a recursive language is recursive  
A language recognized by a nondeterministic Turing machine can also be recognized by a deterministic Turing machine  
Complement of a context free language can be recognized by a Turing machine.  
If a language and its complement are both recursively enumerable then it is recursive  
Complement of a nonrecursive language can never be recognized by any Turing machine. 
Question 35 
Consider the set N^{∗} of finite sequences of natural numbers with x ≤_{p} y denoting that sequence x is a prefix of sequence y. Then, which of the following is true?
N^{∗} is uncountable  
≤_{p} is a total order  
Every nonempty subset of N^{∗} has a least upper bound.  
Every nonempty subset of N^{∗} has a greatest lower bound  
Every nonempty finite subset of N^{∗} has a least upper bound. 
Question 36 
Consider the ordering relation x  y ⊆ N × N over natural numbers N such that xy iff there exists z ∈ N such that x · z = y. A set is called lattice if every finite subset has a least upper bound and greatest lower bound. It is called a complete lattice if every subset has a least upper bound and greatest lower bound. Then,
 is an equivalence relation  
Every subset of N has an upper bound under   
 is a total order.  
(N, ) is a complete lattice  
(N, ) is a lattice but not a complete lattice 
Question 37 
Let f : {0, 1}^{n} → {0, 1} be a boolean function computed by a logical circuit comprising just binary AND and binary OR gates (assume that the circuit does not have any feedback). Let PARITY : {0, 1}^{n} → {0, 1} be the boolean function that outputs 1 iff the total number of input bits set to 1 is odd. Similarly, let MAJORITY be the boolean function that outputs 1 iff the number of input bits that are set to 1 is at least as large as the number of input bits that are set to 0. Then, which of the following is NOT possible?
f(0, 0,..., 0) = f(1, 1,..., 1) = 0.  
f(0, 0,..., 0) = f(1, 1...., 1) = 1  
f is the MAJORITY function.  
f is the PARITY function.  
f outputs 1 at exactly one assignment of the input bits. 
Question 38 
Let k be an integer at least 4 and let [k] = {1, 2 ...,k}. Let f : [k]^{4} → {0, 1} be defined as follows: f(y1, y2, y3, y4)=1 if an only if the yi’s are all distinct. For each choice z = (z1, z2, z3) ∈ [k]^{3}, let g_{z} : [k] → {0, 1} be defined by g_{z}(Y ) = f(Y,z1, z2, z3). Let N be the number of distinct functions g_{z}
that are obtained as z varies in {1, 2,...,k}^{3}, that is, N = {g_{z} : z ∈ {1, 2,...,k}^{3}}. What is N?
k^{3} + 1.  
2^{}  
+ 1  
4 
Question 39 
Consider the following tree with 13 nodes.
Suppose the nodes of the tree are randomly assigned distinct labels from {1, 2,..., 13}, each permutation being equally likely. What is the probability that the labels form a minheap (i.e., every node receives the minimum label in its subtree)?
Suppose the nodes of the tree are randomly assigned distinct labels from {1, 2,..., 13}, each permutation being equally likely. What is the probability that the labels form a minheap (i.e., every node receives the minimum label in its subtree)?
a  
b  
c  
d  
e 
Question 40 
Consider the following game. There is a list of distinct numbers. At any round, a player arbitrarily chooses two numbers a, b from the list and generates a new number c by subtracting the smaller number from the larger one. The numbers a and b are put back in the list. If the number c is nonzero and is not yet in the list, c is added to the list. The player is allowed to play as many rounds as the player wants. The score of a player at the end is the size of the final list.
Suppose at the beginning of the game the list contains the following numbers: 48, 99, 120, 165 and 273. What is the score of the best player for this game?
Suppose at the beginning of the game the list contains the following numbers: 48, 99, 120, 165 and 273. What is the score of the best player for this game?
40  
16  
33  
91  
123 
Question 41 
Consider two independent and identically distributed random variables X and Y uniformly distributed in [0, 1]. For α ∈ [0, 1], the probability that α max(X, Y ) < min(X, Y ) is
1/(2α)  
exp(1 − α)  
1 − α  
(1 − α)^{2}  
1 − α^{2}

Question 44 
A system accepts a sequence of real numbers x[n] as input and outputs
The system is
The system is
nonlinear.  
noncausal.  
timeinvariant  
All of the above  
None of the above 
Question 45 
a1 > a2 > a3  
a1 < a2 < a3  
a1 = 3, a2 = 2, a3 = 4  
All of the above  
None of the above 
Question 46 
g must be identically zero  
g(π/2) = 1.  
g need not be identically zero  
g(π)=0.  
None of the above. 
Question 47 
Let A be an nXn real matrix. It is known that there are two distinct ndimensional real column vectors v1, v2 such that Av1 = Av2. Which of the following can we conclude about A?
All eigenvalues of A are nonnegative.  
A is not full rank  
A is not the zero matrix  
det(A) ≠ 0.  
None of the above 
Question 48 
Consider a square pulse g(t) of height 1 and width 1 centred at 1/2. Define fn(t) = 1/n (g(t) ∗^{n} g(t)), where ∗^{n} stands for nfold convolution. Let f(t) = lim_{n→∞} fn(t). Then, which of the following is TRUE?
The area under the curve of f(t) is zero  
The area under the curve of f(t) is ∞  
f(t) has width ∞ and height 1  
f(t) has width 0 and height ∞.  
None of the above 
Question 49 
Consider the following input x(t) and output y(t) pairs for two different systems.
(i) x(t) = sin(t), y(t) = cos(t),
Which of these systems could possibly be linear and time invariant? Choose the most appropriate answer from below
(i) x(t) = sin(t), y(t) = cos(t),
Which of these systems could possibly be linear and time invariant? Choose the most appropriate answer from below
(i), but not (ii)  
(ii), but not (i).  
both (i) and (ii)  
neither (i) nor (ii).  
neither, but a system with x(t) = sin(2t), y(t) = sin(t) cos(t) could be. 
Question 50 
Consider the two quadrature amplitude modulation (QAM) constellations below. Suppose that the channel has additive white Gaussian noise channel and no intersymbol interference. The constellation points are picked equally likely. Let P(QAM) denote the average transmit power and Pe(QAM) denote the average probability of error under optimal decoding.
Which of the following is TRUE?
Which of the following is TRUE?
P(QAM1) > P(QAM2), Pe(QAM1) < Pe(QAM2)  
P(QAM1) < P(QAM2), Pe(QAM1) > Pe(QAM2)  
P(QAM1) > P(QAM2), Pe(QAM1) > Pe(QAM2)  
P(QAM1) < P(QAM2), Pe(QAM1) < Pe(QAM2).  
P(QAM1) = P(QAM2), Pe(QAM1) = Pe(QAM2). 
Question 51 
It is known that the signal x(t), where t denotes time, belongs to the following class:
{A sin(2πf_{0}t + θ) : f0 = 1Hz, 0 ≤ A ≤ 1, 0 < θ ≤ π}
If you are allowed to take samples of x(t) at times of your choosing, at most how many samples are required to determine the signal?
{A sin(2πf_{0}t + θ) : f0 = 1Hz, 0 ≤ A ≤ 1, 0 < θ ≤ π}
If you are allowed to take samples of x(t) at times of your choosing, at most how many samples are required to determine the signal?
1 sample.  
2 samples.  
1 sample per second.  
2 samples per second.  
None of the above. 
Question 53 
Let function f : R → R be convex, i.e., for x, y ∈ R, α ∈ [0, 1], f(αx + (1 − α)y) ≤ αf(x) + (1 − α)f(y). Then which of the following is TRUE?
f(x) ≤ f(y) whenever x ≤ y.  
For a random variable X, E(f(X)) ≤ f(E(X))  
The second derivative of f can be negative  
If two functions f and g are both convex, then min{f,g} is also convex  
For a random variable X, E(f(X)) ≥ f(E(X)) 
Question 54 
Suppose that a random variable X has a probability density function
f(x) = c(x − 4) for 4 ≤ x ≤ 6
= 0 for all other x
for some constant c. What is the expected value of X given that X ≥ 5
f(x) = c(x − 4) for 4 ≤ x ≤ 6
= 0 for all other x
for some constant c. What is the expected value of X given that X ≥ 5
5*(5/9)  
5*(1/2)  
5*(3/4)  
5*(1/4)  
5*(5/8) 
Question 55 
You are allotted a rectangular room of a fixed height. You have decided to paint the three walls and put wallpaper on the fourth one. Walls can be painted at a cost of Rs. 10 per meter and the wall paper can be put at the rate of Rs 20 per meter for that specified height. What is the minimum cost at which you can achieve this covering for a 200 square meter room?
400 × √3  
400  
400 × √2  
200 × √3  
500 
Question 56 
A fair dice (with faces numbered 1,..., 6) is independently rolled twice. Let X denote the maximum of the two outcomes. The expected value of X is
4*(1/2)  
3*(1/2)  
5  
4*(17/36)  
4*(3/4) 
Question 57 
Let X be a Gaussian random variable with mean μ1 and variance σ^{2}_{1}. Now, suppose that μ1 itself is a
random variable, which is also Gaussian distributed with mean μ2 and variance σ^{2}_{2}. Then the distribution of X is
Gaussian random variable with mean μ2 and variance σ^{2}_{1} + σ^{2}_{2}  
Uniform with mean μ(σ^{2}_{1} + σ^{2}_{2})  
Gaussian random variable with mean μ2 and variance σ^{2}_{1} + σ^{2}_{2}  
Has no known form.  
None of the above. 
Question 58 
A nonnegative loss in a car accident is distributed with the following probability density function
for x ≥ 0. Suppose that first 5 units of loss is incurred by the insured and the remaining loss if any is covered
by the insurance company. What is the expected loss to the insurance company?
for x ≥ 0. Suppose that first 5 units of loss is incurred by the insured and the remaining loss if any is covered
by the insurance company. What is the expected loss to the insurance company?
a  
b  
c  
d  
e 
Question 59 
a  
b  
c  
d  
e 
There are 60 questions to complete.