TIFR GS 2020 Question Paper Computer Science

CSS 2020 Common part Page 1 of 19
1 Common part
1. Two balls are drawn uniformly at random without replacement from a set of five balls
numbered 1, 2, 3, 4, 5. What is the expected value of the larger number on the balls
drawn?
(a) 2.5
(b) 3
(c) 3.5
(d) 4 X

2. Let M be a real n × n matrix such that for every non-zero vector x ∈ Rn , we have
xT M x > 0. Then
(a) Such an M cannot exist.
(b) Such M s exist and their rank is always n. X
(c) Such M s exist, but their eigenvalues are always real.
(d) No eigenvalue of any such M can be real.
(e) None of the above.

3. Let d ≥ 4 and fix w ∈ R. Let

S = a = (a0 , a1 , . . . , ad ) ∈ Rd+1 | fa (w) = 0 and fa0 (w) = 0 ,


Pd i 0
where the polynomial function fa (x) is defined as fa (x) := i=0 ai x and fa (w)
denotes the derivative of fa (x) with respect to x, evaluated at w. Then,
(a) S is finite or infinite depending on the value of α
(b) S is a 2-dimensional vector subspace of Rd+1
(c) S is a d-dimensional vector subspace of Rd+1
(d) S is a (d − 1)-dimensional vector subspace of Rd+1 X
(e) None of the other options

4. Fix n ≥ 4. Suppose there is a particle that moves randomly on the number line,
but never leaves the set {1, 2, . . . , n}. Let the initial probability distribution of the
particle be denoted by ~π . In the first step, if the particle is at position i, it moves to
one of the positions in {1, 2, . . . , i} with uniform distribution; in the second step, if the
particle is in location j, then it moves to one of the locations in {j, j + 1, . . . , n} with
uniform distribution. Suppose after two steps, the final distribution of the particle is
uniform. What is the initial distribution ~π ?
(a) ~π is not unique
(b) ~π is uniform
~ is non-zero for all even i and zero otherwise.
(c) π(i)

CSS 2020 Common part Page 2 of 19
(d) ~π (1) = 1 and ~π (i) = 0 for i 6= 1 X
(e) ~π (n) = 1 and ~π (i) = 0 for i 6= n.

5. Let A be an n × n invertible matrix with real entries whose column sums are all equal
to 1. Consider the following statements:

(1) Every column in the matrix A2 sums to 2.
(2) Every column in the matrix A3 sums to 3.
(3) Every column in the matrix A−1 sums to 1.

Which of the following is TRUE?
(a) none of the statements (1), (2), (3) is correct
(b) statement (1) is correct but not statements (2) or (3)
(c) statement (2) is correct but not statements (1) or (3)
(d) statement (3) is correct but not statements (1) or (2) X
(e) all the 3 statements (1), (2), and (3) are correct

6. What is the maximum number of regions that the plane R2 can be partitioned into
using 10 lines?
(a) 25
(b) 50
(c) 55
(d) 56 X
(e) 1024
Hint: Let A(n) be the maximum number of partitions that can be made by n lines.
Observe that A(0) = 1, A(2) = 2, A(2) = 4 etc. Come up with a recurrence equation
for A(n).

7. A lottery chooses four random winners. What is the probability that at least three
of them are born on the same day of the week? Assume that the pool of candidates
is so large that each winner is equally likely to be born on any of the seven days of
the week independent of the other winners.
17
(a) 2401
48
(b) 2401
105
(c) 2401
175
(d) 2401 X
294
(e) 2401

8. Consider a function f : [0, 1] → [0, 1] which is twice differentiable in (0, 1). Suppose it
has exactly one global maximum and exactly one global minimum inside (0, 1). What
can you say about the behaviour of the first derivative f 0 and and second derivative
f 00 on (0, 1) (give the most precise answer)?

CSS 2020 Common part Page 3 of 19
(a) f is zero at exactly two points, f 00 need not be zero anywhere
0

(b) f 0 is zero at exactly two points, f 00 is zero at exactly one point
(c) f 0 is zero at at least two points, f 00 is zero at exactly one point
(d) f 0 is zero at at least two points, f 00 is zero at at least one point X
(e) f 0 is zero at at least two points, f 00 is zero at at least two points

9. A contiguous part, i.e., a set of adjacent sheets, is missing from Tharoor’s GRE
preparation book. The number on the first missing page is 183, and it is known that
the number on the last missing page has the same three digits, but in a different
order. Note that every sheet has two pages, one at the front and one at the back.
How many pages are missing from Tharoor’s book?
(a) 45
(b) 135
(c) 136 X
(d) 198
(e) 450

10. In a certain year there were exactly four Fridays and exactly four Mondays in January.
On what day of the week did the 20th of January fall that year (recall that January
has 31 days)?
(a) Sunday X
(b) Monday
(c) Wednesday
(d) Friday
(e) None of the others

11. Suppose we toss m = 3 labelled balls into n = 3 numbered bins. Let A be the event
that the first bin is empty while B be the event that the second bin is empty. P (A)
and P (B) denote their respective probabilities. Which of the following is true?
(a) P (A) > P (B)
1
(b) P (A) = 27
(c) P (A) > P (A|B) X
(d) P (A) < P (A|B)

12. The hour needle of a clock is malfunctioning and travels in the anti-clockwise di-
rection, i.e., opposite to the usual direction, at the same speed it would have if it
was working correctly. The minute needle is working correctly. Suppose the the two
needles show the correct time at 12 noon, thus both needles are together at the 12
mark. After how much time do the two needles meet again?
(a) 10/11 hour

CSS 2020 Common part Page 4 of 19
(b) 11/12 hour
(c) 12/13 hour X
(d) 19/22 hour
(e) One hour

13. What is the area of the largest rectangle that can be inscribed in a circle of radius
R?
(a) R2 /2
(b) π × R2 /2
(c) R2
(d) 2R2 X

14. A ball is thrown directly upwards from the ground at a speed of 10 ms−1 , on a planet
where the gravitational acceleration is 10 ms−2 . Consider the following statements:

1. The ball reaches the ground exactly 2 seconds after it is thrown up
2. The ball travels a total distance of 10 metres before it reaches the ground
3. The velocity of the ball when it hits the ground is 10 ms−1

What can you say now?
(a) Only Statement 1 is correct
(b) Only Statement 2 is correct
(c) Only Statement 3 is correct
(d) None of the Statements 1, 2 or 3 is correct
(e) All of the Statements 1, 2 and 3 are correct X

15. The sequence s0 , s1 , . . . , s9 is defined as follows:

s0 = s1 + 1
2si = si−1 + si+1 + 2 for 1 ≤ i ≤ 8
2s9 = s8 + 2.

What is s0 ?
(a) 81
(b) 95
(c) 100 X
(d) 121
(e) 190

CSS 2020 Computer Science Page 5 of 19
2 Computer Science


1. Consider the following Boolean valued function on n Boolean variables: f x1 , . . . , xn =
x1 + · · · + xn (mod 2), where addition is over integers, mapping ‘FALSE’ to 0 and
‘TRUE’ to 1. Consider Boolean circuits (with no feedback) that use only logical
AND and OR gates, and where each gate has two input bits, each of which is either
an input bit of f or the output bit of some other gate of the circuit. The circuit has
a distinguished gate whose value is the output of the circuit. The minimum size of
such a circuit computing f (asymptotically in n) is:
(a) 2o(log n)
(b) nc , for some fixed constant c
(c) nω(1) , but nO(log n)
(d) 2Θ(n)
(e) None of the others X

2. Consider the following statements.

1. The intersection of two context-free languages is always context-free.
2. The super-set of a context-free language is never regular.
3. The subset of a decidable language is always decidable.
4. Let Σ ≡ {a, b, c}. Let L ⊆ Σ be the language of all strings in which either the
number of occurrences of a is the same as the number of occurrences of b OR
the number of occurrences of b is the same as the number of occurrences of c.
Then, L is not context-free.

Which of the above statements are true?
(a) Only (1)
(b) Only (1) and (2)
(c) Only (1),(2) and (3)
(d) Only (4)
(e) None of (1), (2), (3), (4) are true X

3. Consider the (decimal) number 182, whose binary representation is 10110110. How
many positive integers are there in the following set?

{n ∈ N : n ≤ 182 and n has exactly four ones in its binary representation}

(a) 91
(b) 70
(c) 54 X
(d) 35
(e) 27

CSS 2020 Computer Science Page 6 of 19
4. A clamp gate is an analog gate parametrized by two real numbers a and b, and
denoted as clampa,b . It takes as input two non-negative real numbers x and y. Its
output is defined as
(
ax + by when ax + by ≥ 0, and
clampa,b (x, y) =
0 when ax + by < 0.

Consider circuits composed only of clamp gates, possibly parametrized by different
pairs (a, b) of real numbers. How many clamp gates are needed to construct a circuit
that on input non-negative reals x and y outputs the maximum of x and y?
(a) 1
(b) 2 X
(c) 3
(d) 4
(e) No circuit composed only of clamp gates can compute the max function.

5. Let u be a point on the unit circle in the first quadrant (i.e., both coordinates of u
are positive). Let θ be the angle subtended by u and the x axis at the origin. Let
`u denote the infinite line passing through the origin and u. Consider the following
operation Ou on points in the plane.
Operation Ou
INPUT: a point v on the plane

1. Reflect v in the x axis, obtaining ṽ.
2. Reflect ṽ in `u , obtaining v̂.
3. Output v̂.

If v̂ is the output of applying Ou on v, we write Ou (v) = v̂. Further, we denote by
Ouk the iterates of Ou , i.e., Ou1 (v) := Ou (v) and Ouk (v) := Ou (Ouk−1 (v)) for all integers
k > 1.
Consider a point v in the first quadrant such that v and the x-axis subtend an angle
φ at the origin. Define w = Ou8 (v). Assuming θ = 5◦ and φ = 10◦ , what is the angle
subtended by w and the x-axis at the origin?
(a) 50◦
(b) 85◦
(c) 90◦ X
(d) 145◦
(e) 165◦

6. Consider the context-free grammar below ( denotes the empty string, alphabet is
{a, b}):
S → |aSb|bSa|SS.
What language does it generate?

CSS 2020 Computer Science Page 7 of 19
(a) (ab)∗ + (ba)∗
(b) (abba) ∗ +(baab)∗
(c) (aabb)∗ + (bbaa)∗
(d) Strings of the form an bn or bn an , n any positive integer
(e) Strings with equal numbers of a and b X

7. Consider the following algorithm (Note: For positive integers p, q, p/q denotes the
floor of the rational number pq , assume that given p, q, p/q can be computed in one
step):

Input: Two positive integers a, b, a ≥ b.
Output: A positive integer g.
while (b > 0) {
x = a - (a/b)*b;
a = b;
b = x;
}
g = a;

Suppose K is an upper bound on a. How many iterations does the above algorithm
take in the worst case?
(a) Θ(log K) X
(b) Θ(K)
(c) Θ(K log K)
(d) Θ(K 2 )
(e) Θ(2K )

8. Jobs keep arriving at a processor. A job can have an associated time length as well
as a priority tag. New jobs may arrive while some earlier jobs are running. Some jobs
may keep running indefinitely. A starvation free job-scheduling policy guarantees that
no job waits indefinitely for service. Which of the following job-scheduling policies is
starvation free?
(a) Round-robin X
(b) Shortest job first
(c) Priority queuing
(d) Latest job first
(e) None of the others

9. A particular Panini-Backus-Naur Form definition for a <word> is given by the follow-
ing rules:

CSS 2020 Computer Science Page 8 of 19
<word>::= <letter>|<letter><pairlet>|<letter><pairdig>
<pairlet>::= <letter><letter>|<pairlet><letter><letter>
<pairdig>::= <digit><digit>|<pairdig><digit><digit>
<letter>::= a|b|c|...|y|z
<digit>::= 0|1|2|...|9

Which of the following lexical entities can be derived from <word>?

I. word
II. words
III. c22
(a) None of I, II or III
(b) I and II only
(c) I and III only
(d) II and III only X
(e) I, II and III

10. Among the following asymptotic expressions, which of these functions grows the
slowest (as a function of n) asymptotically?
(a) 2log n
(b) n10
√ 2
(c) ( log n)log n
√
(d) (log n) log n
√
log log n
(e) 22 X
11. Which of the following graphs are bipartite?

(1) (2) (3)

(a) Only (1)
(b) Only (2) X
(c) Only (2) and (3)
(d) None of (1),(2), (3)
(e) All of (1), (2), (3)

12. Given the pseudocode below for the function remains(), which of the following
statements is true about the output, if we pass it a positive integer n > 2?

CSS 2020 Computer Science Page 9 of 19
int remains(int n)
{
int x = n;
for (i=(n-1);i>1;i--) {
x = x%i;
}
return x;
}
(a) Output is always 0
(b) Output is always 1 X
(c) Output is 0 only if n is NOT a prime number
(d) Output is 1 only if n is a prime number
13. Let G be an undirected graph. An Eulerian cycle of G is a cycle that traverses each
edge of G exactly once. A Hamiltonian cycle of G is a cycle that traverses each vertex
of G exactly once. Which of the following must be true?
(a) Checking if G has an Eulerian cycle can be done in polynomial time X
(b) Deciding if G has a Hamiltonian cycle is not NP-complete
(c) If G has an Eulerian cycle, then it has a Hamiltonian cycle
(d) A complete graph always has both an Eulerian cycle and a Hamiltonian cycle
(e) All of the other statements are true
14. The figure below describes the network of streets in a city where Motabhai sells
pakoras from his cart. The number next to an edge is the time (in minutes) taken to
traverse the corresponding street.

20
a b

10 30 40
20 30

30 40 20
s c d t

10
40 30 20
10

e 30
f

At present the cart is required to start at point s and, after visiting each street at
least once, reach point t. For example, Motabhai can visit the streets in the following
order
s−a−c−s−e−c−d−a−b−d−f −e−d−b−t−f −d−t

CSS 2020 Computer Science Page 10 of 19
in order to go from s to t. Note that the streets {b, d} and {d, f } are both visited
twice in this strategy. The total time taken for this trip is 440 minutes [which is, 380
(the sum of the traversal times of all streets in the network) + 60 (the sum of the
traversal times of streets {b, d} and {d, f })].
Motabhai now wants the cart to return to s at the end of the trip. So the previous
strategy is not valid, and he must find a new strategy. How many minutes will
Motabhai now take if he uses an optimal strategy?
Hint: s, t, b and f are the only odd degree nodes in the figure above.
(a) 430 X
(b) 440
(c) 460
(d) 470
(e) 480

15. Suppose X1a , X1b , X2a , X2b , ..., X5a , X5b are ten Boolean variables each of which can
take the value TRUE or FALSE. Recall the Boolean XOR X ⊕ Y := (X ∧ ¬Y ) ∨
(¬X ∧ Y ). Define the Boolean logic formulas

F := (X1a ∨ X1b ) ∧ (X2a ∨ X2b ) ∧ (X3a ∨ X3b ) ∧ (X4a ∨ X4b ) ∧ (X5a ∨ X5b ),

Gi := (Xi,a ⊕ Xi+1,a ) ∨ (Xi,b ⊕ Xi+1,b ), 1≤i≤4
G5 := (X5a ⊕ X1a ) ∨ (X5b ⊕ X1b ),
H := F ∧ G1 ∧ G2 ∧ G3 ∧ G4 ∧ G5 .
A truth assignment to the ten Boolean variables Xia , Xib , 1 ≤ i ≤ 5 is said to be a
satisfying assignment if H takes the value TRUE. For example,

(X1a , X1b , X2a , X2b , ..., X5a , X5b ) = (F, T, T, F, F, T, T, T, T, F )

is a satisfying assignment,

(X1a , X1b , X2a , X2b , ..., X5a , X5b ) = (F, T, T, T, F, T, T, T, T, F )

is another satisfying assignment, while

(X1a , X1b , X2a , X2b , ..., X5a , X5b ) = (F, T, T, F, F, T, T, F, T, F )

is not a satisfying assignment.
How many satisfying assignments does H have?
(a) 20
(b) 30 X
(c) 32
(d) 160
(e) 1024

CSS 2020 System Science Page 11 of 19
3 System Science
1. Consider a discrete-time system which in response to input sequence x[n] (n integer)
outputs the sequence y[n] such that

0, n = −1, −2, −3, . . . ,
y[n] =
αy[n − 1] + x[n] + 1, n = 0, 1, 2, . . .

Suppose |α| < 1. Is the system linear, time-invariant, bounded input bounded output
(BIBO) stable?
(a) Linear, time-invariant, BIBO stable
(b) Non-linear, time-invariant, BIBO stable X
(c) Linear, time-variant, BIBO unstable
(d) Non-linear, time-variant, BIBO stable
(e) Cannot be determined from the information given

2. RConvolution between two functions f (t) and g(t) is defined as follows: f (t) ∗ g(t) =
∞
−∞
f (τ )g(t − τ )dτ . If f (t) ∗ g(t) = h(t), what is f (t − 1) ∗ g(t + 1)?
(a) h(2t)
(b) h(t) X
(c) h(t − 1)
(d) h(t + 1)

3. Balls are drawn one after the other uniformly at random without replacement from
a set of eight balls numbered 1, 2, . . . , 8 until all balls drawn. What is the expected
number of balls whose value match their ordinality (i.e., their position in the order
in which balls were drawn)?
Hint: what is the probability that the i-th ball is drawn at the i-th draw? Now can
you use linearity of expectation to solve the problem?
(a) 1 X
(b) 1.5
(c) 2
(d) 2.5

4. Let f, g : R → R be two functions that are continuous and differentiable. Consider
the following statements:

1. min{f, g} is continuous
2. max{f, g} is continuous
3. max{f, g} is differentiable

CSS 2020 System Science Page 12 of 19
Which of the following is TRUE?
(a) Only statement 1 is correct
(b) Only statement 2 is correct
(c) Only statement 3 is correct
(d) Only statements 1 and 2 are correct X

5. Let f (t) be a periodic signal of period 1, i.e. f (t + 1) = f (t) ∀ t. Define the averaging
operator depending on a fixed parameter h > 0 as below:
Z x+h
1
g(x) = f (t)dt.
2h x−h

Which of the following is TRUE for the new signal g(x)?
(a) g(x) is aperiodic
(b) g(x) is periodic with period 21
(c) g(x) is periodic with period 1 X
(d) The value of h determines whether or not g(x) is periodic

6. For all values of r > 0, the area of the set of all points outside the unit square whose
Euclidean distance to the unit square is less than r is:
(a) = πr2 + 4r X
(b) < 4πr2
(c) > 4πr3 + 4r
3
(d) = 4πr
3
+ 6r + 2πr2

7. Given n independent Bernoulli random variables, taking value 1 with probability p
and 0 with probability 1 − p. Then, which of the following is the value of E[(z1 +
. . . zn )2 ]?
(a) 0
(b) np + n(n − 1)p2 X
(c) n3 p2
(d) n2 p2 + np

8. Suppose that Dice 1 has five faces numbered 1 to 5, each of which is equally likely to
occur once the dice is rolled. Dice 2 similarly has eight equally likely faces numbered
1 to 8. Suppose that the two dice are rolled, and the sum is equal to 8. Conditioned
on this, what is the chance that the Dice 1 rolled a number less than or equal to 2?

CSS 2020 System Science Page 13 of 19
(a) 1/4
(b) 1/3
(c) 1/2
(d) 2/7
(e) 2/5 X

9. Let A be an n × n matrix with the the property that Am = 0 for some m ∈ N.
Consider the following statements:

1. At least one entry of A is zero
2. All eigenvalues of A are zero
3. All diagonal entries of A are zero

Which of the following is TRUE?
(a) Only statement 1 is correct
(b) Statement 2 alone is correct X
(c) Only statement 3 is correct
(d) Only statements 1 and 2 are correct
(e) Only statements 2 and 3 are correct

10. Consider two independent random variables (U1 , U2 ) both are uniformly distributed
between [0, 1]. The conditional expectation

E[(U1 + U2 )| max(U1 , U2 ) ≥ 0.5]

equals
(a) 7/6 X
(b) 8/7
(c) 6/7
(d) 1.1

11. Suppose that X is a real valued random variable and E[exp X] = 2. Then, which of
the following must be TRUE? Hint: (exp(x) + exp(y))/2 ≥ exp((x + y)/2).
(a) E[X] < ln 2
(b) E[X] > ln 2
(c) E[X] ≥ ln 2
(d) E[X] ≤ ln 2 X

12. Consider a unit disc D. Let a point x be chosen uniformly on D and let the random
distance to x from the center of D be R. Which of the following is TRUE?

CSS 2020 System Science Page 14 of 19
(a) R is uniformly distributed in [0, 1] X
2

(b) πR2 is uniformly distributed in [0, 1]
(c) π2 R2 is uniformly distributed in [0, 1]
(d) 2πR2 is uniformly distributed in [0, 1]
13. Alice and Bob have one coin each with probability of Heads p and q, respectively.
In each round, both Alice and Bob independently toss their coin once, and the game
stops if one of them gets a Heads and the other gets a Tails. If they both get either
Heads or both get Tails in any round, the game continues. Let R be the expected
number of rounds by which the game stops. Which of the following is TRUE?
1
(a) R = p+q−2pq X
1
(b) R = p+q−p 2 q2

(c) R is independent of p and q
1
(d) R = 1+2pq−p−q
14. Two matrices A and B are called similar if there exists an invertible matrix X such
that A = X −1 BX. Let A and B be two similar matrices. Consider the following
statements:
1. det(xI − A) = det(xI − B) for any scalar x
2. The eigenvalues of A and B are identical
   
1 0 0 1
3. and are similar
0 1 1 0
Which of the following is TRUE?
(a) Only statement 1 is correct
(b) Only statement 2 is correct
(c) Only statements 1 and 2 are correct X
(d) All Statements 1, 2 and 3 are correct
15. Suppose ~u, ~v1 , ~v2 ∈ Rn are linearly independent vectors such that ~v1T ~v2 = 0. Let
the pair of real numbers (a∗1 , a∗2 ) be such that they solve the following optimization
problem
d = min k~u − (a1~v1 + a2~v2 )k,
a1 ,a2 ∈R
n
~ ∈ R we denote its length by kwk.
where for a vector w ~ Let

~v∗ = a∗1~v1 + a∗2~v2
~v = a∗2~v1 + a∗1~v2 .

Compute the inner product ~v∗T ~v .

CSS 2020 System Science Page 15 of 19
(a) ~uT ~v X
(b) k~uk2 − k~v∗ k2
(c) k~v∗ k2 − k~uk2
(d) 0