TIFR PHD CS & SS 2012

Question 1
Amar and Akbar both tell the truth with probability 3/4 and lie with probability 1/4. Amar watches a test match and talks to Akbar about the outcome. Akbar, in turn, tells Anthony, “Amar told me that India won”.
What probability should Anthony assign to India’s win?
A
9/16
B
6/16
C
7/16
D
10/16
E
None of the above
       Engineering-Mathematics       Probability-and-statistics
Question 2
If Mr.M is guilty, then no witness is lying unless he is afraid. There is a witness who is afraid. Which of the following statements is true?
(Hint: Formulate the problem using the following predicates
G – Mr. M is guilty
W(x) – x is a witness
L(x) – x is lying
A(x) – x is afraid )
A
Mr.M is guilty
B
Mr.M is not guilty
C
From these facts one cannot conclude that Mr.M is guilty
D
There is a witness who is lying
E
No witness is lying.
       Engineering-Mathematics       Propositional-Logic
Question 3
Long ago, in a planet far far away, there lived three races of intelligent inhabitants: the Blues (who always tell the truth), the Whites (who always lie), and the Pinks (who, when asked a series of questions, start with a lie and then tell the truth and lie alternately). To three creatures, chosen from the planet and seated facing each other at A, B and C (see figure), the following three questions are put:
(i) What race is your left-hand neighbour?
(ii) What race is your right-hand neighbour?
(iii) What race are you?

Here are their answers:
A: (i) White (ii) Pink (iii) Blue
B: (i) Pink (ii) Pink (iii) Blue
C: (i) White (ii) Blue (iii) Blue
What is the actual race of each of the three creatures?
A
A is Pink, B is White, C is Blue
B
A is Blue, B is Pink, C is White
C
A is Pink, B is Blue, C is Pink
D
A is White, B is pink, C is blue
E
Cannot be determined from the above data
       Aptitude       Numerical
Question 4
Let ABC be a triangle with n distinct points inside. A triangulation of ABC with respect to the n points is obtained by connecting as many points as possible such that no more line segment can be added without intersecting other line segments. In other words, ABC has been partitioned into triangles with end points at the n points or at the vertices A, B, C. For example, the following figure gives one possible triangulation of ABC with two points inside it.

Although there are many different ways to triangulate ABC with the n points inside, the number of triangles depends only on n. In the above figure it is five. How many triangles are there in a triangulation of ABC with n points inside it?
A
3n − 1
B
n2 + 1
C
n + 3
D
2n + 1
E
4n − 3
       Aptitude       Numerical
Question 5
What is the maximum number of points of intersection between the diagonals of a convex octagon (8-vertex planar polygon)? Note that a polygon is said to be convex if the line segment joining any two points in its interior lies wholly in the interior of the polygon. Only points of intersection between diagonals that lie in the interior of the octagon are to be considered for this problem.
A
55
B
60
C
65
D
70
E
75
Question 6
A certain pair of used shoes can be repaired for Rs. 1250 and will last for 1 year. A pair of the same kind of shoes can be purchased new for Rs. 2800 and will last for 2 years. The average cost per year of the new shoes is what percent greater than the cost of repairing the used shoes?
A
5%
B
12%
C
15%
D
3%
E
24%
       Aptitude       Numerical
Question 7
It is required to divide the 2n members of a club into n disjoint teams of 2 members each. The teams are not labelled. The number of ways in which this can be done is:
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics
Question 8
How many pairs of sets (A, B) are there that satisfy the condition A, B ⊆ {1, 2, . . . , 5}, A ∩ B = {}?
A
125
B
127
C
130
D
243
E
257
       Engineering-Mathematics       Set-Theory
Question 9
The probability of throwing six perfect dices and getting six different faces is
A
1 − 6!/66
B
6!/66
C
6-6
D
1-6-6
E
None of the above
       Engineering-Mathematics       Probability-and-statistics
Question 10
In how many different ways can r elements be picked from a set of n elements if
(i) Repetition is not allowed and the order of picking matters?
(ii) Repetition is allowed and the order of picking does not matter?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics
Question 11
Let N be the sum of all numbers from 1 to 1023 except the five primes numbers: 2, 3, 11, 17, 31. Suppose all numbers are represented using two bytes (sixteen bits). What is the value of the least significant byte (the least significant eight bits) of N?
A
00000000
B
10101110
C
01000000
D
10000000
E
11000000
       Digital-Logic-Design       Number-Systems
Question 12
For the polynomial p(x) = 8x10 − 7x3 + x − 1 consider the following statements (which may be true or false)
(i) It has a root between [0, 1].
(ii) It has a root between [0, −1].
(iii) It has no roots outside (−1, 1).
Which of the above statements are true?
A
Only (i)
B
Only (i) and (ii)
C
Only (i) and (iii)
D
Only (ii) and (iii)
E
All of (i), (ii) and (iii)
       Engineering-Mathematics       Polynomials
Question 13
The maximum value of the function
f(x, y, z) = (x − 1/3)2 + (y − 1/3)2 + (z − 1/3)2
subject to the constraints
x + y + z = 1, x ≥ 0, y ≥ 0, z ≥ 0
A
1/3
B
2/3
C
1
D
4/3
E
4/9
       Engineering-Mathematics       Calculus
Question 14
A
B
1
C
1/2
D
0
E
None of the above
       Engineering-Mathematics       Calculus
Question 15
Consider the differential equation dx/dt = (1−x)(2−x)(3−x). Which of its equilibria is unstable?
A
x = 0
B
x = 1
C
x = 2
D
x = 3
E
None of the above
       Engineering-Mathematics       Calculus
Question 16
Walking at 4/5 is normal speed a man is 10 minute too late. Find his usual time in minutes
A
81
B
64
C
52
D
40
E
It is not possible to determine the usual time from given data
       Aptitude       Numerical
Question 17
A spider is at the bottom of a cliff, and is n inches from the top. Every step it takes brings it one inch closer to the top with probability 1/3, and one inch away from the top with probability 2/3, unless it is at the bottom in which case, it always gets one inch closer. What is the expected number of steps for the spider to reach the top as a function of n?
A
It will never reach the top
B
Linear in n
C
Polynomial in n
D
Exponential in n
E
Double exponential in n
       Engineering-Mathematics       Probability-and-statistics
Question 18
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 19
An electric circuit between two terminals A and B is shown in the figure below, where the numbers indicate the probabilities of failure for the various links, which are all independent.

What is the probability that A and B are connected?
A
6/25
B
379/400
C
1/1200
D
1199/1200
E
59/60
       Engineering-Mathematics       Probability-and-statistics
Question 20
There are 1000 balls in a bag, of which 900 are black and 100 are white. I randomly draw 100 balls from the bag. What is the probability that the 101st ball will be black?
A
9/10
B
More than 9/10 but less than 1
C
Less than 9/10 but more than 0
D
0
E
1
       Engineering-Mathematics       Probability-and-statistics
Question 21
For x, y ∈ {0, 1}n, let x ⊕ y be the element of {0, 1}n obtained by the component-wise exclusive-or of x and y. A Boolean function F : {0, 1} n → {0, 1} is said to be linear if F(x ⊕ y) = F(x) ⊕ F(y), for all x and y. The number of linear functions from {0, 1}n to {0, 1} is
A
22n
B
2n+1
C
2n-1+1
D
n!
E
2n
       Digital-Logic-Design       Boolean-Function
Question 22
In a graph, the degree of a vertex is the number of edges incident (connected) on it. Which of the following is true for every graph G?
A
There are even number of vertices of even degree
B
There are odd number of vertices of even degree
C
There are even number of vertices of odd degree
D
There are odd number of vertices of odd degree
E
All the vertices are of even degree
       Engineering-Mathematics       Graph-Theory
Question 23
For a person p, let w(p), A(p, y), L(p) and J(p) denote that p is a woman, p admires y, p is a lawyer and p is a judge respectively. Which of the following is the correct translation in first order logic of the sentence: “All women who are lawyers admire some judge”?
A
∀x : [(w(x) ∧ L(x)) ⇒ (∃y : (J(y) ∧ w(y) ∧ A(x, y)))]
B
∀x : [(w(x) ⇒ L(x)) ⇒ (∃y : (J(y) ∧ A(x, y)))]
C
∀x∀y : [(w(x) ∧ L(x)) ⇒ (J(y) ∧ A(x, y))]
D
∃y∀x : [(w(x) ∧ L(x)) ⇒ (J(y) ∧ A(x, y))]
E
∀x : [(w(x) ∧ L(x)) ⇒ (∃y : (J(y) ∧ A(x, y)))]
       Engineering-Mathematics       Propositional-Logic
Question 24
Let ∧, ∨ denote the meet and join operations of a lattice. A lattice is called distributive if for all x, y, z,
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
It is called complete if meet and join exist for every subset. It is called modular if for all x, y, z,
z ≤ x ⇒ x ∧ (y ∨ z) = (x ∧ y) ∨ z
The positive integers under divisibility ordering i.e. p ≤ q if p divides q forms a
A
complete lattice
B
modular, but not distributive lattice
C
distributive lattice
D
lattice but not a complete lattice
E
under the give ordering positive integers do not form a lattice
       Engineering-Mathematics       Set-Theory
Question 25
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Set-Theory
Question 26
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Set-Theory
Question 27
A bag contains 16 balls of the following colors: 8 red, 4 blue, 2 green, 1 black, and 1 white. Anisha picks a ball randomly from the bag, and messages Babu its color using a string of zeros and ones. She replaces the ball in the bag, and repeats this experiment, many times. What is the minimum expected length of the message she has to convey to Babu per experiment?
A
3/2
B
log 5
C
15/8
D
31/16
E
2
       Engineering-Mathematics       Probability-and-statistics
Question 28
Consider the parse tree

Assume that * has higher precedence than +, − and operators associate right to left (i.e. a + b + c =(a + (b + c))). Consider
(i) 2 + a − b
(ii) 2 + a − b ∗ a + b
(iii) (2 + ((a − b) ∗ (a + b)))
(iv) 2 + (a − b) ∗ (a + b)
The parse tree corresponds to
A
Expression (i)
B
Expression (ii)
C
Expression (iv) only
D
Expression (ii), (iii) and (iv)
E
Expressions (iii) and (iv) only
       Compiler-Design       Parsers
Question 29
Consider the concurrent program
x:=1;
cobegin
x := x + x + 1 || x := x + 2
coend;
Reading and writing of a variable is atomic, but evaluation of an expression is not atomic. The set of possible values of variable x at the end of the execution of the program is
A
{3}
B
{7}
C
{3,5,7}
D
{3,7}
E
{3,5}
       Operating-Systems       Process-Synchronization
Question 30
Consider the blocked-set semaphore where the signaling process awakens any one of the suspended proceses; i.e.,
Wait(S): If S > 0 then S ← S − 1, else suspend the execution of this process.
Signal(S): If there are processes that have been suspended on semaphore S, then wake any one of them,
else S ← S + 1.
Consider the following solution of mutual exclusion problem using blocked-set semaphores.
S :=1;
cobegin
P(1) || P(2) || ... || P(N)
coend
where the task body P(i) is
begin
while true do
begin

Wait(S)

Signal(S)
end
end
Here N is the number of concurrent processors. Which of the following is true?
A
The program fails to achieve mutual exclusion of critical regions
B
The program achieves mutual exclusion; but starvation freedom is ensured only for N ≤ 2
C
The program does not ensure mutual exclusion if N ≥ 3
D
The program achieves mutual exclusion, but allows starvation for any N ≥ 2
E
The program achieves mutual exclusion and starvation freedom for any N ≥ 1
       Operating-Systems       Process-Synchronization
Question 31
Consider the following three versions of the binary search program. Assume that the elements of type T can be compared with each other; also assume that the array a is sorted.
i,j,k : integer;
a : array [1..N] of T;
x :T;
Program 1 : i := 1; j := N;
repeat
k := (i+j)div 2;
if a[k] < x then i := k else j := k
until (a[k] = x) or (i > j)
Program 2 : i := 1; j := N;
repeat
k := (i+j) div 2;
if x < a [k] then j := k-1;
if a[k] < x then i := k+1;
until i > j
Program 3 : i := 1; j := N;
repeat
k := (i+j) div 2;
if x < a[k] then j := k else i := k+1
until i > j
A binary search program is called correct provided it terminates with a[k] = x whenever such an element exists, or it terminates with a[k] 6= x if there exists no array element with value x.
Which of the following statements is correct?
A
Only Program 1 is correct
B
Only Program 2 is correct
C
Only Programs 1 and 2 are correct
D
Both Programs 2 and 3 are correct
E
All the three programs are wrong
       Algorithms       Searching
Question 32
Let A be a matrix such that Ak = 0. What is the inverse of I − A?
A
0
B
I
C
A
D
1 + A + A2 + · · · + Asup>k−1
E
Inverse is not guaranteed to exist
       Engineering-Mathematics       Linear-Algebra
Question 33
An array A contains n integers. We wish to sort A in ascending order. We are told that initially no element of A is more than a distance k away from its final position in the sorted list. Assume that n and k are large and k is much smaller than n. Which of the following is true for the worst case complexity of sorting A?
A
A can be sorted with constant · kn comparisons but not with fewer comparisons
B
A cannot be sorted with less than constant · n log n comparisons
C
A can be sorted with constant · n comparisons
D
A can be sorted with constant · n log k comparisons but not with fewer comparisons
E
A can be sorted with constant · k2n comparisons but not fewer
       Algorithms       Sorting
Question 34
Consider the quicksort algorithm on a set of n numbers, where in every recursive subroutine of the algorithm, the algorithm chooses the median of that set as the pivot. Then which of the following statements is TRUE?
A
The running time of the algorithm is Θ(n).
B
The running time of the algorithm is Θ(n log n)
C
The running time of the algorithm is Θ(n1.5).
D
The running time of the algorithm is Θ(n2)
E
None of the above.
       Algorithms       Sorting
Question 35
Let T be a tree on n nodes. Consider the following algorithm, that constructs a sequence of leaves u1, u2, . . .. Let u1 be some leaf of tree. Let u2 be a leaf that is farthest from u1. Let u3 be the leaf that is farthest from u2, and, in general, let ui+1 be a leaf of T that is farthest from ui (if there are many choices for ui+1, pick one arbitrarily). The algorithm stops when some ui is visited again. What can you say about the distance between ui and ui+1, as i = 1, 2, ...?
A
For some trees, the distance strictly reduces in each step
B
For some trees, the distance increases initially and then decreases
C
For all trees, the path connecting u2 and u3 is a longest path in the tree.
D
For some trees, the distance reduces initially, but then stays constant.
E
For the same tree, the distance between the last two vertices visited can be different, based on the choice of the first leaf u1.
       Data-Structures       Trees
Question 36
Consider a complete binary tree of height n, where each edge is a one Ohm resistor. Suppose all the leaves of the tree are tied together. Approximately how much is the effective resistance from the root to this bunch of leaves for very large n?
A
Exponential in n
B
Cubic in n
C
Linear in n
D
Logarithmic in n
E
Of the order square root of n
       Data-Structures       Binary-Trees
Question 36 Explanation: 
Question and answer is wrong.
Question 37
Which of the following correctly describes LR(k) parsing?
A
The input string is alternately scanned left to right and right to left with k reversals.
B
Input string is scanned once Left to Right with rightmost derivation and k symbol look-ahead
C
LR(k) grammers are expressively as powerful as context-free grammers.
D
Parser makes k left-to-right passes over input string
E
Input string is scanned from left to right once with k symbol to the right as look-ahead to give left-most derivation.
       Compiler-Design       Parsers
Question 38
Let ai denote a sequence a · a · · · a with i letters and let ℵ be the set of natural numbers {1, 2, · · · }
Let L1 = {aib2i | i ∈ ℵ} and L2 = {aibi2 | i ∈ ℵ} be two langauges.
Which of the following is correct?
A
Both L1 and L2 are context free languages.
B
L1 is context-free and L2 is recursive but not context-free
C
Both L1 and L2 are recursive but not context-free
D
L1 is regular and L2 is context-free.
E
Complement of L2 is context-free
       Theory-of-Computation       Languages-and-Grammars
Question 39
Which of the following statements is TRUE?
A
Every Turing machine recognizable language is recursive
B
The complement of every recursively enumerable language is recursively enumerable
C
The complement of a recursive language is recursively enumerable.
D
The complement of a context free language is context free
E
The set of turing machines which do not halt on empty input forms a recursively enumerable set
       Theory-of-Computation       Languages-and-Grammars
Question 40
This question concerns the classes P and NP. If you are familiar with them, you may skip the definitions and go directly to the question.
Let L be a set. We say that L is in P if there is some algorithm which given input x decides if x is in L or not in time bounded by a polynomial in the length of x. For example, the set of all connected graphs is in P, because there is an algorithm which, given a graph graph, can decide if it is connected or not in time roughly proportional to the number of edges of the graph.
The class NP is a superset of class P. It contains those sets that have membership witnesses that can be verified in polynomial time. For example, the set of composite numbers is in NP. To see this take the witness for a composite number to be one of its divisors. Then the verification process consists of performing just one division using two reasonable size numbers. Similarly, the set of those graphs that have a Hamilton cycle, i.e. a cycle containing all the vertices of the graph, is in in NP. To verify that the graph has a Hamilton cycle we just check if the witnessing sequence of vertices indeed a cycle of the graph that passes through all the vertices of the graph. This can be done in time that is polynomial in the size of the graph.
More precisely, if L is a set in P consisting of elements of the form (x, w), then the set

A
a
B
b
C
c
D
d
E
e
       Algorithms       P-NP
Question 41
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Calculus
Question 41 Explanation: 
Given question and answer is wrong.
Question 42
Let α1, α2, · · · , αk be complex numbers. Then

is
A
0
B
C
αk
D
α1
E
maxjj |
       Engineering-Mathematics       Calculus
Question 43
A
a
B
b
C
c
D
d
E
None of the above statements are true
Question 44
A
a
B
b
C
c
D
d
E
e
Question 45
Consider a periodic square wave f(t) with a period of 1 second such that f(t) = 1 for t ∈ [0, 1/2) and f(t) = −1 for t ∈ [1/2, 1). It is passed through an ideal low-pass filter with cutoff at 2 Hz. Then the output is
A
sin(2πt)
B
cos(2πt)
C
sin(2πt) − sin(6πt)/3 + sin(10πt)/5 − ...
D
sin(2πt) − cos(2πt)
E
None of the above
Question 46
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Calculus
Question 47
A linear time-invariant system has a transfer function H(s) = 1/(1 + s). If the input to the system is cos(t), the output is
A
(ejt + e-jt)/2 where j =√−1
B
cos(t)/2
C
(cos(t) + sin(t))/2
D
sin(t)/2.
E
The system is unstable and the output is not well-defined
Question 48
The input to a series RLC circuit is a sinusoidal voltage source and the output is the current in the circuit. Which of the following is true about the magnitude frequency response of this system?
A
Dependending on the values of R, L and C, a steady state may not exist, and the magnitude frequency response is not well-defined.
B
It is low-pass with 3 dB bandwidth 1/(2π√(LC)).
C
It is high-pass with 3 dB bandwidth 1/(2π√(LC)).
D
It is low-pass and the 3-dB bandwidth depends on all: R, L, C
E
It is 0 at DC, decays to zero as frequency increases to infinity, and has a maximum at 1/(2π√LC)
Question 49
A
resample y(t) at 16 kHz and sinc interpolate using T =1/8 ms
B
resample y(t) at 8 kHz and sinc interpolate using T =1/16 m
C
send y(t) over a low pass filter of bandwidth 4 kHz
D
any of the above
E
none of the above
Question 50
Suppose three dice are rolled independently. Each dice can take values 1 to 6 with equal probability. Find the probability that the second highest outcome equals the average of the other two outcomes. Here, the ties may be resolved arbitrarily.
A
1/6
B
1/9
C
39/216
D
7/36
E
43/216
       Engineering-Mathematics       Probability-and-statistics
Question 51
A Poisson random variable X is given by Pr{X = k} = e−λλk/k!, k = 0, 1, 2, ... for λ > 0. The variance of X scales as
A
λ
B
λ2
C
λ3
D
√λ
E
None of the above
       Engineering-Mathematics       Probability-and-statistics
Question 52
In modelling the number of health insurance claims filed by an individual during a three year period, an analyst makes a simplifying assumption that for all non-negative integer up to 5,

where pn denotes the probability that a health insurance policy holder files n claims during this period. The analyst assumes that no individual files more than 5 claims in this period. Under these assumptions, what is the probability that a policy holder files more than two claims in this period?
A
7/31
B
29/125
C
1/3
D
13/125
E
None of the above
       Engineering-Mathematics       Probability-and-statistics
Question 53
Consider a single amoeba that at each time slot splits into two with probability p or dies otherwise with probability 1 − p. This process is repeated independently infinitely at each time slot, i.e. if there are any amoebas left at time slot t, then they all split independently into two amoebas with probability p or die with probability 1 − p. Which of the following is the expression for the probability that the race of amoeba becomes extinct

A
a
B
b
C
c
D
d
E
None of the above
       Engineering-Mathematics       Probability-and-statistics
Question 54
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Calculus
Question 55
Consider a string of length 1 m. Two points are chosen independently and uniformly random on it thereby dividing the string into three parts. What is the probability that the three parts can form the sides of a triangle?
A
1/4
B
1/3
C
1/2
D
2/3
E
3/4
       Engineering-Mathematics       Probability-and-statistics
Question 56
Let P be a n × n matrix such that Pk = 0, for some k ∈ N and where 0 is an all zeros matrix. Then at least how many eigenvalues of P are zero
A
1
B
n-1
C
n
D
0
E
None of the above
       Engineering-Mathematics       Linear-Algebra
Question 57
Let A = UΛU† be a n × n matrix, where UU† = I. Which of the following statements is TRUE
A
The matrix I + A has non-negative eigen values
B
The matrix I + A is symmetic
C
det(I + A) = det(I + Λ)
D
(a) and (c)
E
(a), (b) and (c)
       Engineering-Mathematics       Linear-Algebra
Question 58
Under a certain coordinate transformation from (x, y) to (u, v) the circle x2 + y2 = 1 shown below on the left side was transformed into the ellipse shown on the right side.
A1 only
B
A2 only
C
A1 or A2
D
A1 or A3
E
A2 or A3
Question 59
X and Y are two 3 by 3 matrices. If
then
A
X has rank 2
B
at least one of X, Y is not invertible
C
X can’t be an invertible matrix
D
X and Y could both be invertible
E
None of the above
       Engineering-Mathematics       Linear-Algebra
Question 60
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Linear-Algebra
There are 60 questions to complete.