TIFR PHD CS & SS 2014

Question 1
Consider the reactions
X + 2Y → 3Z
2X + Z → Y.
Let nX, nY , nZ denote the numbers of molecules of chemicals X, Y , Z in the reaction chamber. Then
which of the following is conserved by both reactions?
A
nX + nY + nZ
B
nX + 7nY + 5nZ
C
2nX + 9nY - 3nZ
D
3nX - 3nY + 13nZ
E
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.
A
log 5
B
log 29/log 25
C
e5
D
1 + log6 5
E
None of the above
Question 3
The Fibonacci sequence is defined as follows: F0 = 0, F1 = 1, and for all integers n ≥ 2,
Fn = Fn-1 + Fn-2. Then which of the following statements is FALSE?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics
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
0
B
5
C
100
D
Infinite
E
None of the above
       Engineering-Mathematics       Combinatorics
Question 5
The rules for the University of Bombay five-a-side 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?
A
23
B
91
C
60
D
49
E
None of the above
       Engineering-Mathematics       Combinatorics
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?
A
1/2
B
2/3
C
3/4
D
5/6
E
6/7
       Engineering-Mathematics       Probability-and-statistics
Question 7
Consider a sequence of non-negative numbers {xn : n = 1, 2,...}. Which of the following statements cannot be true?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics
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?
A
Only claim 1 follows
B
Only claim 2 follows
C
Either claim 1 or claim 2 follows but not both
D
Neither claim 1 nor claim 2 follows
E
Both claim 1 and claim 2 follow
       Aptitude       Numerical
Question 9
Solve min x2 + y2
subject to
x + y ≥ 10,
2x + 3y ≥ 20,
x ≥ 4,
y ≥ 4.
A
32
B
50
C
52
D
100
E
None of the above
       Engineering-Mathematics       Inequality
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 hour-hand and the minute-hand of her (well-functioning) 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
A
Twenty five minutes past 4pm
B
Twenty six and 122/143 minutes past 4pm
C
Twenty seven and 1/3 minutes past 4pm.
D
Twenty eight minutes past 4pm
E
None of the above
       Aptitude       Numerical
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?
A
51:49
B
1:1
C
49:51
D
51:98
E
98:51
       Aptitude       Numerical
Question 12
A
The above inequality holds under conditions (1) and (2) but not under condition (3).
B
The above inequality holds under conditions (2) and (3) but not under condition (1)
C
The above inequality holds under conditions (1) and (3) but not under condition (2).
D
The above inequality holds under all the three conditions
E
The above inequality holds under none of the three conditions
       Engineering-Mathematics       Inequality
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 co-ordinate system (and leaving L untouched), the new intercepts are a and b respectively. Which of the following is TRUE?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Co-ordinate-Geometry
Question 14
Let m and n be any two positive integers. Then, which of the following is FALSE?
A
m + 1 divides m2n − 1
B
For any prime p, mp ≡ m (modp)
C
If one of m, n is prime, then there are integers x, y such that mx + ny = 1
D
If m
E
If 2n − 1 is prime, then n is prime.
       Aptitude       Numerical
Question 15
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Calculus
Question 16
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Calculus
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).
A
6*(5/6)
B
6
C
5*(1/2)
D
6*(1/3)
E
5*(2/3)
       Engineering-Mathematics       Probability-and-statistics
Question 18
A
a
B
b
C
c
D
d
E
e
Question 19
Consider the following random function of x
F(x)=1+ Ux + Vx2 mod 5,
where U and V are independent random variables uniformly distributed over {0, 1, 2, 3, 4}. Which of the
following is FALSE?
A
F(1) is uniformly distributed over {0, 1, 2, 3, 4}.
B
F(1), F(2) are independent random variables and both are uniformly distributed over {0, 1, 2, 3, 4}
C
F(1), F(2), F(3) are independent and identically distributed random variables.
D
All of the above.
E
None of the above
       Engineering-Mathematics       Probability-and-statistics
Question 20
Consider the equation x2 +y2 −3z2 −3t2 = 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
A
200
B
55
C
100
D
1
E
None of the above
       Engineering-Mathematics       Polynomials
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 in-order (visit left subtree, visit root, visit right subtree) and post-order (visit left subtree, visit right subtree, visit root) traversals of T produce the following sequences.
in-order: a, b, c, d, e, f, g, h, i, j, k
post-order: a, c, b, e, f, h, j, k, i, g, d
How many leaves does the tree have?
A
THREE.
B
FOUR.
C
FIVE.
D
SIX.
E
Cannot be determined uniquely from the given information
       Data-Structures       Binary-Trees
Question 22
Consider the following code.
def brian(n):
count = 0
while ( n != 0 )
n = n & ( n-1 )
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 8-bit) representation of 22 is 00010110 and the binary representation of 15 is 00001111, and the bit-wise AND of these binary strings is 00000110, which is the binary representation of 6. What does the function brian return?
A
The highest power of 2 dividing n, but zero if n is zero
B
The number obtained by complementing the binary representation of n.
C
The number of ones in the binary representation of n.
D
The code might go into an infinite loop for some n.
E
The result depends on the number of bits used to store unsigned integers
       Programming       Control-Statement
Question 23
Consider the following directed graph.

Suppose a depth-first 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
A
B = 1, C = 1, and T = 4.
B
B = 0, C = 2, and T = 4.
C
B = 2, C = 1, and T = 3.
D
B = 1, C = 2, and T = 3
E
B = 2, C = 2, and T = 1.
       Data-Structures       BFS-and-DFS
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?
A
cost(a, b) ≥ 6.
B
cost(b, e) ≥ 5
C
cost(e, f) ≥ 5.
D
cost(a, d) ≥ 4
E
cost(b, c) ≥ 4
       Algorithms       Minimum-Spanning-Tree
Question 25
Let G = (V,E) be an undirected connected simple (i.e., no parallel edges or self-loops) 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?
A
The tree T has to contain the edge e1
B
The tree T has to contain the edge e2.
C
The minimum weight edge incident on each vertex has to be present in T
D
T is the unique minimum spanning tree in G.
E
If we replace each edge weight wi = w(ei) by its square w2i , then T must still be a minimum spanning tree of this new instance.
       Algorithms       Minimum-Spanning-Tree
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?
A
O(1)
B
Hn = ∑ni=1 1/i
C
√n
D
n/2
E
n
       Engineering-Mathematics       Probability-and-statistics
Question 27
Which of the following statements is TRUE for all sufficiently large n?
A
a
B
b
C
c
D
d
E
e
       Algorithms       Asymptotic-Complexity
Question 28
Which of these functions grows fastest with n?
A
en/n
B
en−0.9 log n
C
2n
D
(log n)n−1
E
None of the above
       Engineering-Mathematics       Calculus
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?
A
These three elements can be determined using O(log2 n) comparisons
B
O(log2 n) comparisons do not suffice, however these three elements can be determined using n+O(1) comparisons.
C
n + O(1) comparisons do not suffice, however these three elements can be determined using n + O(log n) comparisons
D
n+O(log n) comparisons do not suffice, however these three elements can be determined using O(n) comparisons.
E
None of the above
       Algorithms       Time-Complexity
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?
A
These two elements can be determined using O(log100 n) comparisons
B
O(log100 n) comparisons do not suffice, however these two elements can be determined using n + O(log n) comparisons
C
n+O(log n) comparisons do not suffice, however these two elements can be determined using 3⌈n/2 ⌉ comparisons
D
3⌈n/2 ⌉ comparisons do not suffice, however these two elements can be determined using 2(n − 1) comparisons
E
None of the above.
       Algorithms       Time-Complexity
Question 31
Consider the following recurrence relation:

Which of the following statements is FALSE?
A
T(n) is O(n3/2) when k = 3
B
T(n) is O(n log n) when k = 3
C
T(n) is O(n log n) when k = 4
D
T(n) is O(n log n) when k = 5.
E
T(n) is O(n) when k = 5.
       Algorithms       Recurrences
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?
A
true, false, true
B
false, false, true
C
true, false, true
D
false, false, false
E
true, true, true
       Theory-of-Computation       Regular-Language
Question 33
Let L be a given context-free language over the alphabet {a, b}. Construct L1, L2 as follows.
Let L1 = L − {xyx | x, y ∈ {a, b}}, and L2 = L · L. Then
A
Both L1 and L2 are regular
B
Both L1 and L2 are context free but not necessarily regular
C
L1 is regular and L2 is context free.
D
L1 and L2 both may not be context free
E
L1 is regular but L2 may not be context free
       Theory-of-Computation       Languages-and-Grammars
Question 34
Which the following is FALSE?
A
Complement of a recursive language is recursive
B
A language recognized by a non-deterministic Turing machine can also be recognized by a deterministic Turing machine
C
Complement of a context free language can be recognized by a Turing machine.
D
If a language and its complement are both recursively enumerable then it is recursive
E
Complement of a non-recursive language can never be recognized by any Turing machine.
       Theory-of-Computation       Languages-and-Grammars
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?
A
N is uncountable
B
p is a total order
C
Every non-empty subset of N has a least upper bound.
D
Every non-empty subset of N has a greatest lower bound
E
Every non-empty finite subset of N has a least upper bound.
       Engineering-Mathematics       Set-Theory
Question 36
Consider the ordering relation x | y ⊆ N × N over natural numbers N such that x|y 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,
A
| is an equivalence relation
B
Every subset of N has an upper bound under |
C
| is a total order.
D
(N, |) is a complete lattice
E
(N, |) is a lattice but not a complete lattice
       Engineering-Mathematics       Set-Theory
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?
A
f(0, 0,..., 0) = f(1, 1,..., 1) = 0.
B
f(0, 0,..., 0) = f(1, 1...., 1) = 1
C
f is the MAJORITY function.
D
f is the PARITY function.
E
f outputs 1 at exactly one assignment of the input bits.
       Digital-Logic-Design       Boolean-Function
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 gz : [k] → {0, 1} be defined by gz(Y ) = f(Y,z1, z2, z3). Let N be the number of distinct functions gz that are obtained as z varies in {1, 2,...,k}3, that is, N = |{gz : z ∈ {1, 2,...,k}3|}. What is N?
A
k3 + 1.
B
2
C
D
+ 1
E
4
       Engineering-Mathematics       Relations-and-Functions
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 min-heap (i.e., every node receives the minimum label in its subtree)?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Probability-and-statistics
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 non-zero 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?
A
40
B
16
C
33
D
91
E
123
       Aptitude       Numerical
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
A
1/(2α)
B
exp(1 − α)
C
1 − α
D
(1 − α)2
E
1 − α2
       Engineering-Mathematics       Probability-and-statistics
Question 42
A
e
B
1
C
21/3
D
0
E
None of the above
       Engineering-Mathematics       Calculus
Question 43
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Probability-and-statistics
Question 44
A system accepts a sequence of real numbers x[n] as input and outputs

The system is
A
non-linear.
B
non-causal.
C
time-invariant
D
All of the above
E
None of the above
Question 45
A
a1 > a2 > a3
B
a1 < a2 < a3
C
a1 = 3, a2 = 2, a3 = 4
D
All of the above
E
None of the above
       Engineering-Mathematics       Linear-Algebra
Question 46
A
g must be identically zero
B
g(π/2) = 1.
C
g need not be identically zero
D
g(π)=0.
E
None of the above.
       Engineering-Mathematics       Calculus
Question 47
Let A be an nXn real matrix. It is known that there are two distinct n-dimensional real column vectors v1, v2 such that Av1 = Av2. Which of the following can we conclude about A?
A
All eigenvalues of A are non-negative.
B
A is not full rank
C
A is not the zero matrix
D
det(A) ≠ 0.
E
None of the above
       Engineering-Mathematics       Linear-Algebra
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 n-fold convolution. Let f(t) = limn→∞ fn(t). Then, which of the following is TRUE?
A
The area under the curve of f(t) is zero
B
The area under the curve of f(t) is ∞
C
f(t) has width ∞ and height 1
D
f(t) has width 0 and height ∞.
E
None of the above
       Engineering-Mathematics       Calculus
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
A
(i), but not (ii)
B
(ii), but not (i).
C
both (i) and (ii)
D
neither (i) nor (ii).
E
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?
A
P(QAM1) > P(QAM2), Pe(QAM1) < Pe(QAM2)
B
P(QAM1) < P(QAM2), Pe(QAM1) > Pe(QAM2)
C
P(QAM1) > P(QAM2), Pe(QAM1) > Pe(QAM2)
D
P(QAM1) < P(QAM2), Pe(QAM1) < Pe(QAM2).
E
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πf0t + θ) : 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
1 sample.
B
2 samples.
C
1 sample per second.
D
2 samples per second.
E
None of the above.
Question 52
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Probability-and-statistics
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?
A
f(x) ≤ f(y) whenever x ≤ y.
B
For a random variable X, E(f(X)) ≤ f(E(X))
C
The second derivative of f can be negative
D
If two functions f and g are both convex, then min{f,g} is also convex
E
For a random variable X, E(f(X)) ≥ f(E(X))
       Engineering-Mathematics       Calculus
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
A
5*(5/9)
B
5*(1/2)
C
5*(3/4)
D
5*(1/4)
E
5*(5/8)
       Engineering-Mathematics       Probability-and-statistics
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?
A
400 × √3
B
400
C
400 × √2
D
200 × √3
E
500
       Aptitude       Numerical
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
A
4*(1/2)
B
3*(1/2)
C
5
D
4*(17/36)
E
4*(3/4)
       Engineering-Mathematics       Probability-and-statistics
Question 57
Let X be a Gaussian random variable with mean μ1 and variance σ21. Now, suppose that μ1 itself is a random variable, which is also Gaussian distributed with mean μ2 and variance σ22. Then the distribution of X is
A
Gaussian random variable with mean μ2 and variance σ21 + σ22
B
Uniform with mean μ(σ21 + σ22)
C
Gaussian random variable with mean μ2 and variance σ21 + σ22
D
Has no known form.
E
None of the above.
       Engineering-Mathematics       Probability-and-statistics
Question 58
A non-negative 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?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Probability-and-statistics
Question 59
A
a
B
b
C
c
D
d
E
e
Question 60
A
0
B
π/2
C
1/√2
D
2/π
E
None of the above
       Engineering-Mathematics       Calculus
There are 60 questions to complete.