TIFR PHD CS & SS 2015
Question 1 |
Consider a 6-sided die with all sides not necessarily equally likely such that probability of an even number is P({2,4,6})=1/2, probability of a multiple of 3 is P({3,6})=1/3, and probability of 1 is P({1})=1/6. Given the above conditions, choose the strongest (most stringent) condition of the following that must always hold about P({5}), the probability of 5
P({5})=1/6 | |
P({5})≥1/6 | |
P({5})≤1/6 | |
P({5})≤1/3 | |
None of the above |
Question 2 |
Consider a circle with a circumference of one unit length. Let d < 1/6. Suppose that we independently throw two arcs, each of length d, randomly on this circumference so that each arc is uniformly distributed along the circle circumference. The arc attaches itself exactly to the circumference so that arc of length d exactly covers length d of the circumference. What can be said about the probability that the two arcs do not intersect each other?
It equals (1 — d) | |
It equals (1 — 3d) | |
It equals (1 — 2d) | |
It equals 1 | |
It equals (1 — d)(1 — d) |
Question 3 |

Can’t be determined | |
1/(1 - z) | |
1/(1 + z) | |
1 - z9 | |
None of the above |
Question 4 |
The Boolean function obtained by adding an inverter to each and every input of an AND gate is:
OR | |
XOR | |
NAND | |
NOR | |
None of the above |
Question 5 |
What is logically equivalent to “If Kareena and Parineeti go to the shopping mall then it is raining”:
If Kareena and Parineeti do not go to the shopping mall then it is not raining. | |
If Kareena and Parineeti do not go to the shopping mall then it is raining. | |
If it is raining then Kareena and Parineeti go to the shopping mall. | |
If it is not raining then Kareena and Parineeti do not go to the shopping mall. | |
None of the above |
Question 6 |
Ram has a fair coin, i.e., a toss of the coin results in either head or tail and each event happens with probability exactly half (1/2). He repeatedly tosses the coin until he gets heads in two consecutive tosses. The expected number of coin tosses that Ram does is
2 | |
4 | |
6 | |
8 | |
None of the above |
Question 7 |
A 1 X 1 chessboard has one (1) square, a 2 X 2 chessboards has five (5) squares. Continuing along this fashion, what is the number of squares on the (regular) 8 X 8 chessboard?
64 | |
65 | |
204 | |
144 | |
256 |
Question 8 |
There is a set of 2n people: n male and n female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is
2n | |
n2 | |
![]() | |
![]() | |
none of the above |
Question 9 |
Consider a square of side length 2. We throw five points into the square. Consider the following statements:
(i) There will always be three points that lie on a straight line.
(ii) There will always be a line connecting a pair of points such that two points lie on one side of the line and one point on the other.
(iii) There will always be a pair of points which are at distance at most √2 from each other.
Which of the above is true:
(i) There will always be three points that lie on a straight line.
(ii) There will always be a line connecting a pair of points such that two points lie on one side of the line and one point on the other.
(iii) There will always be a pair of points which are at distance at most √2 from each other.
Which of the above is true:
(i) only | |
(ii) only | |
(iii) only | |
(ii) and (iii) | |
None of the above |
Question 11 |
Suppose that f(x) is a continuous function such that 0.4 ≤ f(x) ≤ 0.6 for 0 ≤ x ≤ 1. Which of the following is always true?
f(0.5) = 0.5 | |
There exists x between 0 and 1 such that f(x) = 0.8x | |
There exists x between 0 and 0.5 such that f(x) = x. | |
f(0.5) > 0.5. | |
None of the above statements are always true. |
Question 12 |
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) < XY is
1/(2α) | |
exp(1 - α) | |
1 - α | |
(1 - α)2 | |
1 - α2 |
Question 13 |
Imagine the first quadrant of the real plane as consisting of unit squares. A typical square has 4 corners: (i, j), (i + 1, j), (i + 1,j + 1), and (i, j + 1), where (i, j) is a pair of non-negative integers. Suppose a line segment ℓ connecting (0, 0) to (90, 1100) is drawn. We say that ℓ passes through a unit square if it passes through a point in the interior of the square. How many unit squares does ℓ pass through?
98,990 | |
9,900 | |
1,190 | |
1,180 | |
1,010 |
Question 16 |
Consider the following recurrence relation:
Which of the following statements is TRUE?

Which of the following statements is TRUE?
T(n) is O(log n). | |
T(n) is O(log n • log log n) but not O(log n). | |
T(n) is O(log3/2 n) but not O(log n • log log n). | |
T(n) is O(log2 n) but not O(log3/2 n). | |
T(n) is O(log2 n • log log n) but not O(log2 n). |
Question 17 |
Consider the following undirected connected graph G with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second-best minimum spanning tree is a spanning tree whose weight is the smallest among all spanning trees that are not minimum spanning trees in G.
Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)

Which of the following statements is TRUE in the above graph? (Note that all the edge weights are distinct in the above graph)
There is more than one minimum spanning tree and similarly, there is more than one maximum spanning tree here. | |
There is a unique minimum spanning tree, however there is more than one maximum spanning tree here. | |
There is more than one minimum spanning tree, however there is a unique maximum spanning tree here. | |
There is more than one minimum spanning tree and similarly, there is more than one second-best minimum spanning tree here. | |
There is a unique minimum spanning tree, however there is more than one second-best minimum spanning tree here. |
Question 18 |
Consider the following code fragment in the C programming language when run on a non-negative integer n.
int f(int n)
{
if(n==0 || n==1) return 1;
else
return f(n-1) + f(n-2);
}
Assuming a typical implementation of the language, what is the running time of this algorithm and how does it compare to the optimal running time for this problem?
int f(int n)
{
if(n==0 || n==1) return 1;
else
return f(n-1) + f(n-2);
}
Assuming a typical implementation of the language, what is the running time of this algorithm and how does it compare to the optimal running time for this problem?
This algorithm runs in polynomial time in n but the optimal running time is exponential in n. | |
This algorithm runs in exponential time in n and the optimal running time is exponential in n. | |
This algorithm runs in exponential time in n but the optimal running time is polynomial in n. | |
This algorithm runs in polynomial time in n and the optimal running time is polynomial in n. | |
The algorithm does not terminate |
Question 19 |
First, consider the tree on the left.
On the right, the nine nodes of the tree have been assigned numbers from the set {1, 2,. .., 9} so that for every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree are less than all numbers in the other subtree). How many such assignments are possible? Hint: Fix a value for the root and ask what values can then appear in its left and right subtrees.

On the right, the nine nodes of the tree have been assigned numbers from the set {1, 2,. .., 9} so that for every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree are less than all numbers in the other subtree). How many such assignments are possible? Hint: Fix a value for the root and ask what values can then appear in its left and right subtrees.
29 = 512 | |
24 • 32 • 5 • 9 = 6480 | |
23 • 3 • 5 • 9 = 1080 | |
24 = 16 | |
23 • 33 = 216 |
Question 21 |
Let B consist of all binary strings beginning with a 1 whose value when converted to decimal is divisible by 7.
B can be recognised by a deterministic finite state automaton. | |
B can be recognised by a non-deterministic finite state automaton but not by a deterministic finite state automaton. | |
B can be recognised by a deterministic push-down automaton but not by a non-deterministic finite state automaton. | |
B can be recognised by a non-deterministic push-down automaton but not by a deterministic push-down automaton. | |
B cannot be recognised by any push down automaton, deterministic or non-deterministic |
Question 22 |
Let a, b, c be regular expressions. Which of the following identities is correct ?
(a + b)* = a*b* | |
a(b + c) = ab + c | |
(a + b)* = a* + b* | |
(ab + a)*a = a(ba + a)* | |
None of the above |
Question 24 |

Every Boolean expression is equivalent to an expression in sum of products form. | |
Every Boolean expression is equivalent to an expression in product of sum form. | |
Every Boolean expression is equivalent to an expression without _ operator. | |
Every Boolean expression is equivalent to an expression without ^ operator. | |
Every Boolean expression is equivalent to an expression without ¬ operator. |
Question 26 |
Let Kn be the complete graph on n vertices labelled {1, 2,. .., n} with m = n(n — 1)/2 edges. What is the number of spanning trees of Kn?


a | |
b | |
c | |
d | |
e |
Question 27 |

a | |
b | |
c | |
d | |
e |
Question 29 |
Consider the following concurrent program (where statements separated by || within cobegin-coend are executed concurrently).
x:=1;
cobegin
x:= x+1 || x:= x+1 || x:=x+1
coend
Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values of x at the end of execution of the program is
x:=1;
cobegin
x:= x+1 || x:= x+1 || x:=x+1
coend
Reading and writing of variables is atomic but evaluation of expressions is not atomic. The set of possible values of x at the end of execution of the program is
{4} | |
{2, 3, 4} | |
{2, 4} | |
{2, 3} | |
{2} |
Question 31 |
For a time-invariant system, the impulse response completely describes the system if the system is
causal and non-linear | |
non-causal and non-linear | |
causal and linear | |
All of the above | |
None of the above |
Question 33 |
Let h(t) be the impulse response of an ideal low-pass filter with cut-o↵ frequency 5kHz. Let g[n] = h(nT), for integer n, be a sampled version of h(t) with sampling frequency 1=10kHz. The discrete time filter with g[n] as its unit impulse response is a
low-pass filter | |
high-pass filter | |
band-pass filter | |
band-stop filter | |
all-pass filter |
Question 34 |
The capacity of a certain additive white Gaussian noise channel of bandwidth 1 MHz is known to be 8 Mbps when the average transmit power constraint is 50 mW. Which of the following statements can we make about the capacity C (in Mbps) of the same channel when the average transmit power is allowed to be 100 mW?
C = 8 | |
8 < C < 16 | |
C = 16 | |
C > 16 | |
There is not enough information to determine C |
Question 35 |

Low-pass filter | |
High-pass filter | |
Band-pass filter | |
Band-stop filter | |
All-pass filter |
Question 37 |

det(A) = 9 | |
det(A) = 18 | |
det(A) = 14 | |
det(A) = 27 | |
None of the above |
Question 38 |
Let X and Y be two independent and identically distributed random variables. Let Z = max(X, Y ) and W = min(X, Y ). Which of the following is true?
Z and W are independent | |
E(XZ) = E(YW) | |
E(XY ) = E(ZW) | |
(a), (b), and (c) | |
(a) and (b) only |
Question 39 |
Consider a random variable X that takes integer values 1 through 10 each with equal probability. Now consider random variable
Y = min(7, max(X, 4)).
What is the variance of Y ?
Y = min(7, max(X, 4)).
What is the variance of Y ?
121/4 | |
37/20 | |
9/5 | |
99/12 | |
None of the above |
Question 42 |
Consider the following optimization problem
max (2x + 3y)
subject to the following three constraints
x + y ≤ 5,
x + 2y ≤ 10, and
x < 3.
Let z* be the smallest number such that 2x + 3y ≤ z* for all (x, y) which satisfy the above three constraints. Which of the following is true?
max (2x + 3y)
subject to the following three constraints
x + y ≤ 5,
x + 2y ≤ 10, and
x < 3.
Let z* be the smallest number such that 2x + 3y ≤ z* for all (x, y) which satisfy the above three constraints. Which of the following is true?
There is no (x, y) that satisfies the above three constraints. | |
All (x, y) that satisfy the above three constraints have 2x + 3y strictly less than z* | |
There are exactly two (x, y) that satisfy the above three constraints such that 2x + 3y equals z* | |
There is a unique (x, y) that satisfies the above three constraints such that 2x + 3y equals z* | |
There are infinitely many (x, y) that satisfy the above three constraints such that 2x + 3y equals z* |
Question 43 |

only negative eigenvalues | |
only non-zero eigenvalues | |
only positive eigenvalues | |
one negative and one positive eigenvalue | |
None of the above |
Question 44 |
Consider a frog that lives on two rocks A and B and moves from one rock to the other randomly. If it is at Rock A at any time, irrespective of which rocks it occupied in the past, it jumps back to Rock A with probability 2/3 and instead jumps to Rock B with probability 1/3. Similarly, if it is at Rock B at any time, irrespective of which rocks it occupied in the past, it jumps back to Rock B with probability 2/3 and instead jumps to Rock A with probability 1/3. After the first jump, it is at Rock A. What is the limiting probability that it is at Rock A after a total of n jumps as n --> ∞?
1/2 | |
2/3 | |
1 | |
The limit does not exist | |
None of the above |
There are 45 questions to complete.