TIFR GS 2011 Question Paper Computer Science

Part A
Common Questions
1. If either wages or prices are raised, there will be inflation. If there is infla-
tion, then either the government must regulate it or the people will suffer. If
the people suffer, the government will be unpopular. Government will not be
unpopular. Which of the following can be validly concluded from the above
statements.

(a) People will not suffer
(b) If the inflation is not regulated, then wages are not raised
(c) Prices are not raised
(d) If the inflation is not regulated, then the prices are not raised
(e) Wages are not raised

2. In how many ways can the letters of the word ABACUS be rearranged such
that the vowels always appear together?

(a) (6+3)!
2!
(b) 6!
2!
(c) 3!3!
2!
(d) 4!3!
2!

3. The probability of three consecutive heads in four tosses of a fair coin is

(a) 41
(b) 18
1
(c) 16
3
(d) 16

4. Consider the problem of maximising x2 − 2x + 5 such that 0 < x < 2. The value
of x at which the maximum is achieved is:

(a) 0.5
(b) 1
(c) 1.5
(d) 1.75

1

5. Three distinct points x, y, z lie on a unit circle of the complex plane and satisfy
x + y + z = 0. Then x, y, z form the vertices of

(a) An isosceles but not equilateral triangle
(b) An equilateral triangle
(c) a triangle of any shape
(d) a triangle whose shape can’t be determined

6. Assume that you are flipping a fair coin, i.e. probability of heads or tails is equal.
Then the expected number of coin flips required to obtain two consecutive heads
for the first time is

(a) 4
(b) 3
(c) 6
(d) 10
(e) 5

7. Let X and Y be two independent and identically distributed random variables.
Then P (X > Y ) is

(a) 12
(b) 1
(c) 0
(d) 13
(e) Information is insufficient

8. The sum of the first n terms of the series 1, 11, 111, 1111, · · · , is
1
(a) 81 (10n+1 − 9n − 10)
1
(b) 81 (10n − 9n)
(c) 91 (10n+1 − 1)
(d) 91 (10n+1 − n10n )

2

9. You have to play three games with opponents A and B in a specified sequence.
You win the series if you win two consecutive games. A is a stronger player
than B. Which sequence maximizes your chance of winning the series?

(a) AAB
(b) ABA
(c) BAB
(d) BAA
(e) All are the same

10. Let m, n denote two integers from the set {1, 2, · · · , 10}. The number of ordered
pairs (m, n) such that 2m + 2n is divisible by 5 is

(a) 10
(b) 14
(c) 24
(d) 8
R1
11. 0 loge (x)dx =

(a) 1
(b) -1
(c) ∞
(d) −∞

12. The action for this problem takes place in an island of knights and knaves, where
knights always make true statements and knaves always make false statements
and everybody is either a knight or a knave. Two friends A and B live in a
house. The census taker (an outsider) knocks on the door and it is opened by A.
The census taker says “I need information about you and your friend. Which if
either is a knight and which if either is a knave?”. “We are both knaves” says A
angrily and slams the door. What, if anything can the census taker conclude?

(a) A is a knight and B is a knave
(b) A is a knave and B is a knight
(c) Both are knaves
(d) Both are knights
(e) No conclusion can be drawn

3

√
3−i
13. If z = 2
and (z 95 + i67 )97 = z n , then the smallest value of n is

(a) 1
(b) 10
(c) 11
(d) 12

14. The limit
d sin2 (x)
lim
x→0 dx x
is

(a) 0
(b) 2
(c) 1
(d) 1/2

15. The exponent of 3 in the product 100! is

(a) 27
(b) 33
(c) 44
(d) 48

16. A variable that takes thirteen possible values can be communicated using

(a) thirteen bits
(b) three bits
(c) log2 13 bits
(d) four bits

4

17. What is
2x − 1
lim
x→0 x
(a) 0
(b) log2 (e)
(c) loge (2)
(d) 1

18. The equation of the tangent to the unit circle at point (cos α, sin α) is

(a) x cos α − y sin α = 1
(b) x sin α − y cos α = 1
(c) x cos α + y sin α = 1
(d) x sin α − y cos α = 1

19. Three dice are rolled independently. What is the probability that the highest
and the lowest value differ by 4?

(a) 1/3
(b) 1/6
(c) 1/9
(d) 5/18
(e) 2/9

20. Let n > 1 be an odd integer. The number of zeros at the end of the number
99n + 1 is

(a) 1
(b) 2
(c) 3
(d) 4

5

Part B
Computer Science
21. Let S = {x1 , . . . , xn } be a set of n numbers. Consider the problem of storing
the elements of S in an array A[1..n] such that the following min-heap property
is maintained for all 2 ≤ i ≤ n: A[bi/2c] ≤ A[i]. (Note that bxc is the largest
integer that is at most x.) Which of the following statements is TRUE?

(a) This problem can be solved in O(log n) time.
(b) This problem can be solved in O(n) time but not in O(log n) time.
(c) This problem can be solved in O(n log n) time but not in O(n) time.
(d) This problem can be solved in O(n2 ) time but not in O(n log n) time.

22. Consider the program P :: x:=1; y:=1; z:=1; u:=0
and the program Q :: x,y,z,u := 1,1,1,1; u:=0
Which of the following is true?

(a) P and Q are equivalent for sequential processors.
(b) P and Q are equivalent for all multi-processor models.
(c) P and Q are equivalent for all multi-core machines.
(d) P and Q are equivalent for all networks of computers.

23. Suppose (S1 , S2 , . . . , Sm ) is a finite collection of non-empty subsets of a universe
U . Note that the sets in this collection need not be distinct. Consider the
following basic step to be performed on this sequence. While there exist sets Si
and Sj in the sequence, neither of which is a subset of the other, delete them
from the sequence, and

(i) if Si ∩ Sj 6= ∅, then add the sets Si ∪ Sj and Si ∩ Sj to the sequence;
(ii) if Si ∩ Sj = ∅, then add only the set Si ∪ Sj to the sequence.

In each step we delete two sets from the sequence and add at most two sets
to the sequence. Also, note that empty sets are never added to the sequence.
Which of the following statements is TRUE?

(a) The size of the smallest set in the sequence decreases in every step.
(b) The size of the largest set in the sequence increases in every step.
(c) The process always terminates.
(d) The process terminates if U is finite but might not if U is infinite.
(e) There is a finite collection of subsets of a finite universe U and a choice of
Si and Sj in each step such that the process does not terminate.

6

24. Consider the program
x:=0; y:=0; (r1:=x; r2:=x; y:= if r1 = r2 then 1 || r3:=y ; x:= r3)
Note that || denotes the parallel operator. In which of the following cases can
the program possibly result in a final state with r1 = 0; r2 = r3 = 1.

(a) Such a transformation is not possible in Java.
(b) Such a program transformation is possible in Java.
(c) Possible in Pascal when the compiler appropriately translates the || oper-
ator to interleaved Pascal statements.
(d) Possible in all sequential programming languages when the compiler ap-
propriately translates the || operator to interleaved statements in the se-
quential language.

25. Let AT M be defined as follows:

AT M = {hM, wi|The Turing machine M accepts the word w}.

and let L be some NP-complete language. Which of the following statements is
FALSE?

(a) L ∈ N P .
(b) Every problem in N P is polynomial time reducible to L.
(c) Every problem in N P is polynomial time reducible to AT M .
(d) Since L is NP-complete, AT M is polynomial time reducible to L.
(e) AT M ∈
/ NP .

26. Consider the following two scenarios in the dining philosophers problem: (i)
First a philosopher has to enter a room with the table that restricts the number
of philosophers to four. (ii) There is no restriction on the number of philosophers
entering the room. Which of the following is true?

(a) Deadlock is possible in (i) and (ii).
(b) Deadlock is possible in (i).
(c) Starvation is possible in (i).
(d) Deadlock is not possible in (ii).
(e) Starvation is not possible in (ii).

7

27. Let n be a large integer. Which of the following statements is TRUE?
√ 1 p 1
(a) n log2 n < log2 n < n 100
1 √ 1 p
(b) n 100 < n log2 n < log2 n
√ 1
1 p
(c) n log2 n < n 100 < log2 n
√ 1
p 1
(d) log2 n < n log2 n < n 100
p 1 √ 1
(e) log2 n < n 100 < n log2 n

28. Consider a basic block x:= a[i]; a[j]:=y; z:=a[j] optimized by removing common
subexpression a[i] as follows: x:= a[i]; z:=x; a[j]:= y. Which of the following is
true?

(a) Both are equivalent.
(b) The values computed by both are exactly the same.
(c) Both give exactly the same values only if i is not equal to j.
(d) They will be equivalent in concurrent programming languages with shared
memory.

29. You are given ten rings numbered from 1 to 10, and three pegs labeled A, B
and C. Initially all the rings are on peg A, arranged from top to bottom in
ascending order of their numbers. The goal is to move all the rings to peg B in
the minimum number of moves obeying the following constraints:

i. In one move, only one ring can be moved.
ii. A ring can only be moved from the top of its peg to the top of a new peg.
iii. At no point can a ring be placed on top of another ring with a lower
number.

How many moves are required?

(a) 501
(b) 1023
(c) 2011
(d) 10079

8

30. Consider an array A[1..n]. It consists of a permutation of numbers 1..n. Now
compute another array B[1..n] as follows: B[A[i]]:= i for all i. Which of the
following is true?

(a) B will be a sorted array.
(b) B is a permutation of array A.
(c) Doing the same transformation twice will not give the same array.
(d) B is not a permutation of array A.

31. Given a set of n = 2k distinct numbers, we would like to determine the smallest
and the second smallest using comparisons. Which of the following statements
is TRUE?

(a) Both these elements can be determined using 2k comparisons.
(b) Both these elements can be determined using n − 2 comparisons.
(c) Both these elements can be determined using n + k − 2 comparisons.
(d) 2n − 3 comparisons are necessary to determine these two elements.
(e) nk comparisons are necessary to determine these two elements.

32. Various parameter passing mechanisms have been in used in different program-
ming languages. Which of the following statements is true?

(a) Call by value result is used in language Ada
(b) Call by value result is the same as call by name.
(c) Call by value is the most robust.
(d) Call by reference is the same as call by name.
(e) Call by name is the most efficient.

33. Which of the following is NOT a sufficient and necessary condition for an undi-
rected graph G to be a tree?

(a) G is connected and has n − 1 edges.
(b) G is acyclic and connected.
(c) G is acyclic and has n − 1 edges.
(d) G is acyclic, connected and has n − 1 edges.
(e) G has n − 1 edges.

9

34. Consider the class of synchronization primitives. Which of the following is false?

(a) Test and set primitives are as powerful as semaphores.
(b) There are various synchronizations that can be implemented using an array
of semaphores but not by binary semaphores.
(c) Split binary semaphores and binary semaphores are equivalent.
(d) All statements a-c are false.
(e) Petri nets with and without inhibitor arcs have the same power.

35. Let G be a connected simple graph (no self-loops or parallel edges) on n ≥ 3
vertices, with distinct edge weights. Let e1 , e2 , . . . , em be an ordering of the edges
in decreasing order of weight. Which of the following statements is FALSE?

(a) The edge e1 has to be present in every maximum weight spanning tree.
(b) Both e1 and e2 have to be present in every maximum weight spanning tree.
(c) The edge em has to be present in every minimum weight spanning tree.
(d) The edge em is never present in any maximum weight spanning tree.
(e) G has a unique maximum weight spanning tree.

36. Consider malware programs. Which of the following is true?

(a) A worm is a parasite
(b) A virus cannot affect a linux operating system.
(c) A trojan can be in the payload of only a worm.
(d) A worm and virus are self replicating programs
(e) There is no difference between a virus and a worm.

37. Given an integer n ≥ 3, consider the problem of determining if there exist
integers a, b ≥ 2 such that n = ab . Call this the forward problem. The reverse
problem is: given a and b, compute ab (mod b). Note that the input length
for the forward problem is blog nc + 1, while the input length for the reverse
problem is blog ac + blog bc + 2. Which of the following statements is TRUE?

(a) Both the forward and reverse problems can be solved in time polynomial
in the lengths of their respective inputs.
(b) The forward problem can be solved in polynomial time, however the reverse
problem is NP-hard.
(c) The reverse problem can be solved in polynomial time, however the forward
problem is NP-hard.
(d) Both the forward and reverse problems are NP-hard.

10

38. Consider the class of recursive and iterative programs. Which of the following
is false?

(a) Recursive programs are more powerful than iterative programs.
(b) For every iterative program there is an equivalent recursive program.
(c) Recursive programs require dynamic memory management.
(d) Recursive programs do not terminate sometimes.
(e) Iterative programs and recursive programs are equally expressive.

39. The first n cells of an array L contain positive integers sorted in decreasing
order, and the remaining m − n cells all contain 0. Then, given an integer x, in
how many comparisons can one find the position of x in L?

(a) At least n comparisons are necessary in the worst case.
(b) At least log m comparisons are necessary in the worst case.
(c) O(log(m − n)) comparisons suffice.
(d) O(log n) comparisons suffice.
(e) O(log(m/n)) comparisons suffice.

40. Consider the class of object oriented languages. Which of the following is true?

(a) Pascal is an object oriented language.
(b) Object oriented languages require heap management.
(c) Object oriented languages cannot be implemented in language C.
(d) Object oriented languages are more powerful than declarative program-
ming languages.
(e) Parallelism cannot be realized in object oriented languages.

11

Part C
Systems Science
41. Output of a linear system with input x(t) is given by
Z ∞
y(t) = h(t, τ )x(τ ) + 1.
−∞

The system is linear if

(a) h(t, τ ) = h(t − τ )
(b) h(t, τ ) = h(τ )
(c) h(t, τ ) = h(t)
(d) h(t, τ ) = constant

42. The minimum number of unit delay elements required for realizing an infinite
impulse response (IIR) filter is/are

(a) 0.
(b) 1.
(c) ∞.
(d) > 1.

43. The Fourier transform of
tn−1 −at
x(t) = e u(t), a > 0
(n − 1)!
√
( = −1, u(t) = 1 for t ≥ 0, u(t) = 0, t < 0) is

(a) (a + ω)n
Pn (a+ω)k
(b) k=1 k!
(c) naω
1
(d) (a+ω)n

44. Let limn→∞ xn = x. Then which of the following is TRUE.

(a) There exists an n0 , such that for all n > n0 , |xn − x| = 0.
(b) There exists an n0 , such that for all n > n0 , |xn − x| ≤  for any  > 0.
(c) For every  > 0, there exists an n0 , such that for all n > n0 , |xn − x| ≤ .
(d) There exists an n0 , such that for all n > n0 , | xxn | ≤  for any  > 0.

12

45. Consider a system with input x(t) and the output y(t) is given by

y(t) = x(t) − 0.5x(t − 1) − 0.5x(t − 2) + 1.
The system is

(a) Linear
(b) Non-causal
(c) Time varying
(d) All of the above

46. Let H(z) be the z-transform of the transfer function corresponding to an input
output relation y(n)− 12 y(n−1) = x(n)+ 31 x(n−1). Then which of the following
is TRUE

(a) The ROC of H(z) is |z| > 12 .
(b) The ROC of H(z) is |z| < 21 .
(c) Both (a) and (b).
(d) System is necessarily causal.

47. Assume you are using a binary code error correcting code C. If the minimum
Hamming distance between any two codewords of C is 3. Then

(a) We can correct and detect 2 bit errors.
(b) We can correct 1 bit errors and detect 2 bit errors.
(c) We can correct 2 bit errors and detect 1 bit errors.
(d) We can correct 1 bit errors and detect 1 bit errors.

48. Let f (x, y) be a function in two variables x, y. Then which of the following is
true

(a) maxx miny f (x, y) ≤ miny maxx f (x, y).
(b) maxx miny f (x, y) ≥ miny maxx f (x, y).
(c) maxx miny f (x, y) = miny maxx f (x, y).
(d) maxx miny f (x, y) = miny maxx f (x, y) + miny minx f (x, y).

13

49. Consider two independent random variables X and Y having probability density
functions uniform in the interval [−1, 1]. The probability that X 2 + Y 2 > 1 is

(a) π/4
(b) 1 − π/4
(c) π/2 − 1
(d) Probability that X 2 + Y 2 < 0.5

50. Let f (x) = |x|, for x ∈ (−∞, ∞). Then

(a) f (x) is not continuous but differentiable.
(b) f (x) is continuous and differentiable.
(c) f (x) is continuous but not differentiable.
(d) f (x) is neither continuous nor differentiable.

51. What is the value of λ such that Prob{X > mean{X}} = 1/e, where PDF of
X is pX (x) = λe−λx , x ≥ 0, λ > 0?

(a) 1
(b) 1/e
√
(c) 1/ e
(d) 1/e2
(e) All of the above

52. Consider two communication systems C1 and C2 that use pulse amplitude mod-
ulation (PAM), P AM1 and P AM2 . Let the distance between any two points of
P AM1 be d, and P AM2 be 2d, respectively. Assume that C1 and C2 are cor-
rupted by additive white Gaussian noise of variance σ 2 and 2σ 2 , respectively.
Let P1 and P2 be the probability of error for C1 and C2 . Then

(a) P1 = P2 .
(b) P1 < P2 .
(c) P1 > P2 .
(d) P1 = P2 + 21 .

14

53. If ak is an increasing function of k, i.e. a1 < a2 < . . . < ak . . .. Then which of
the following is TRUE.

(a) limn→∞ nk=1 a1k = ∞.
P

(b) limn→∞ nk=1 |a1k | < ∞.
P

(c) Either (a) or (b).
(d) limn→∞ nk=1 a1k = 0.
P

54. In household electrical wiring which configuration is used to connect different
electrical equipments.

(a) Series.
(b) Parallel
(c) Combination of series and parallel.
(d) Any of the above.

55. Consider a channel where xn ∈ {0, 1} is the input and yn = xn ∗zn is the output,
where ∗ is EX-OR operation, and P (zn = xn−1 ) = P (zn = yn−1 ) = 21 . Note
that communication starts at time n = 0, and assume x−1 = y−1 = 0. Then the
capacity of the channel in bits is

(a) 12 .
(b) 1.
(c) < 1.
(d) ≥ 0.
(e) Both (c) and (d).

56. Consider a triangular shaped pulse x of base 2T and unit height centered at 0,
i.e. x(t) = 0 for |t| > T , x(t) = 1 − |t| for t ∈ [−T, T ]. Then if x is convolved
with itself, the output is

(a) Square shape.
(b) Triangular shape.
(c) Bell shape.
(d) Inverted U shape.

15

57. Let x[n] and y[n] be the input and output of a linear time invariant (LTI)
system. Then which of following system is LTI.

(a) z[n] = y[n] + c for a constant c.
(b) z[n] = x[n]y[n].
(c) z[n] = y[n] + x[n] + c for a constant c.
(d) z[n] = y[n] + x[n].

58. Which of the following statements is TRUE.

(a) The cascade of a non-causal linear time invariant (LTI) system with a
causal LTI system can be causal.
(b) If h[n] ≤ 2 for all n, then the LTI system with h[n] as its impulse response
is stable and causal.
(c) If the impulse response h[n] of a LTI system is of finite duration then the
LTI system is stable and causal.
(d) With h[n] = 3n u[−n + 10], where u[n] = 1, n ≥ 0, u[n] = 0, n < 0, the LTI
system is stable.
(e) Both (c) and (d).

59. Let RX (τ ) be the autocorrelation function of a zero mean stationary random
process X(t). Which of following statements is FALSE.

(a) If RX (τ ) = 0, ∀τ , X(n) and X(m), n 6= m are independent.
(b) RX (τ ) = RX (−τ ).
(c) RX (0) = E[X 2 ], where E denotes the expectation.
(d) RX (0) ≥ RX (τ ), ∀τ .

60. Let x(t) be a signal whose Fourier transform X(f ) is zero for |f | > W . Using a
sampler with sampling frequency 4W , which of the following filters can be used
to exactly reconstruct x(t).

(a) Low pass filter spanning frequencies [-W W].
(b) Band pass filter spanning frequencies [3W 5W].
(c) Band pass filter spanning frequencies [-3W 5W].
(d) All the above.

16