TIFR GS 2024 Question Paper Computer Science

GS 2024 Common Section: Solutions Page 1 of 11

Common Section
1. If O is the center of the circle, what is the area of the shaded portion in square cm?

4cm

4cm

O

√
(a) 4π − 4 2
7
√
(b)
2
π − 4 2
7
√
(c)
2
π−4 3
√
(d) 83 π − 4 3 ✓
8
√
(e)
3
π−4 2

2. Let σ be a uniform random permutation of {1, . . . , 100}. What is the probability
that σ(1) < σ(2) < σ(3) (i.e., what is the probability that the
rst three elements
are in increasing order)?

In the options below, n! = 1 × 2 × . . . × n.

3
(a)
100!
3!
(b)
100!
6
(c)
100
1
(d) ✓
6
1
(e)
3
3. There is a 100cm long ruler that has 11 ants on positions 0cm, 10cm, 20cm, 30cm,
..., 100cm. The ant at the 0cm mark is facing towards the 100cm mark, and the ant
at the 100cm is facing towards the 0cm mark; all other ants is either facing towards
0cm or towards the 100cm mark.
All ants start moving in the direction they are facing at a speed of 1cm per second.
Whenever an ant collides with another ant, the two instantly reverse their direction
and continue moving in the other direction. All ants continue moving until they fall
o the ruler when they move past one of the two ends (at 0cm or 100cm marks).

How long will it take for all ants to fall o the ruler?

(a) At most 50 seconds, but cannot be determined without knowing the direc-
tions of all ants.

GS 2024 Common Section: Solutions Page 2 of 11

(b) 50 seconds.

(c) At least 50 seconds and at most 100 seconds, but cannot be determined
without knowing the directions of all ants.

(d) 100 seconds. ✓
(e) More than 100 seconds, but cannot be determined without knowing the
directions of all ants.

4. Let z1 , z2 , z3 , . . . , z2023 be a permutation of the numbers 1, 2, 3, . . . , 2023. Which of
Q2023
the following is true about the product i=1 (zi − i)?
Note: The parity of an integer n just denotes whether n is even or odd. Formally,
the parity of n is said to be odd if n is odd, and even if n is even.

(a) The above product is always even. ✓
(b) The above product is always odd.

(c) The parity of the above product always changes if we swap the values of
any two variables among z1 , z2 , . . . , z2023 .

(d) There always exist two variables among z1 , z2 , . . . , z2023 such that the par-
ity of the above product changes if we swap their values, but there may
also exist two variables among the z1 , z2 , . . . , z2023 such that swapping their
values does not change the parity of the above product.

(e) None of the above statements is true.

5. Let p(x) be a polynomial with real coe
cients which satis
es p(r) = p(−r) for every
real number r . Let n ≥ 5 be a positive integer. Suppose that p(i) = i for all 1 ≤ i ≤ n.
5
What is the maximum possible value of the absolute value of the coe
cient of x in
p(x)?
(a) 0 ✓
(b) 5

(c) 10

(d) n
(e) n+1

6. For each month in the year (i.e., January, February, March,...), let us assume the
probability that a person's birthday falls in that particular month is exactly 1/12,
and let us assume that this is independent for dierent persons.

What is the smallest value of the natural number n such that, among n independently
chosen persons the probability that there is a pair of them born in the same month
is at least 1/2?

(a) 3

(b) 4

(c) 5 ✓
(d) 6

GS 2024 Common Section: Solutions Page 3 of 11

(e) 7

7. Let S := {(a, b) | 0 ≤ a ≤ 1 , 0 ≤ b ≤ 1}, a unit square, in R2 . Let B :=
{(x, y) | x2 + y 2 ≤ 1}, a unit disk, in R2 . De
ne the set S + B as follows:

S + B := {(u, v) | ∃(a, b) ∈ S , (x, y) ∈ B such that u = a + x , v = b + y} .

What is the area of S + B ?

(a) π+4
(b) π + 5 ✓
(c) π+3
(d) π+2
(e) None of the above.

8. A palindrome is a string that reads the same in reverse (e.g. ABBA or KAYAK or
MALAYALAM).

How many strings of length 5 using the letters from {A, B, C, D, E} have no palin-
dromic substring of length at least 2?

(a) 243

(b) 405

(c) 540 ✓
(d) 675

(e) 1280
R∞ 1
9. Compute 16 x
· √√1 dx.
x−1

(a) 0
π
(b)
3
π
(c)
2
2π
(d) 3 ✓
(e) 2π

10. Let M be a 3 × 3 matrix over the real numbers such that M T M = I. Consider the
following statements.

3
(i) There exists a non-zero vector x ∈ R such that M x = 0.
3
(ii) There exist two non-zero vectors x, y ∈ R such that the angle between them
and that between M x and M y are dierent.

(iii) There exists a non-zero vector x such that its length is dierent from that of
M x.

Which of the above statements is/are true?

(a) Only (i).

GS 2024 Common Section: Solutions Page 4 of 11

(b) Only (ii).

(c) Only (iii).

(d) All three statements.

(e) None of the three statements. ✓

11. Consider the following sequence of polynomials with real coe
cients.

P0 (x) = 1
P1 (x) = 2x
Pn+1 (x) = 2xPn (x) − Pn−1 (x), for all natural numbers n ≥ 1.

What is the dimension of the linear span of the set

{P0 (x), P1 (x), P2 (x), P3 (x), P4 (x)}

in the vector space of polynomials in variable x with real coe
cients?

(a) 1
(b) 2
(c) 3
(d) 4
(e) 5 ✓

12. A subset S of the rational numbers is said to be nice if for every in
nite sequence
of x1 , x2 , . . . of elements from S , there is always two indices i < j such that xi ≤ xj .
Consider the following statements.

(i) The set of natural numbers IN is nice.

(ii) The set of integers Z is nice.

(iii) The set of positive rational numbers is nice.

Which of the above statements is/are true?

(a) Only (i). ✓
(b) Only (i) and (ii).

(c) Only (i) and (iii).

(d) All three statements are true.

(e) None of the three statements is true.

13. Let n ≥ 100 be a positive integer. X1 , X2 , . . . , Xn be independent random
Let
2
variables, each taking values in the set {0, 1} such that Pr[Xi = 1] = for each
Pn 3
1 ≤ i ≤ n. De
ne S := i=1 Xi , and let p(x) be a polynomial such that for each
j ′
non-negative integer j , the coe
cient of x in p(x) is Pr[S = j]. What is p (1)?

Note: p′ (x) denotes the polynomial obtained by dierentiating p with respect to x.
(a) 0

GS 2024 Common Section: Solutions Page 5 of 11

(b) n
(c) 2n
3
✓
4n2 +2n
(d)
9
4n2 −4n
(e)
9

14. Let A and B be two n × n invertible matrices with real entries such that every row in
A sums to 1 and every row in B sums to 2. Consider the following three statements:

(i) Every row in the matrix AB sums to 2.
−1
(ii) Every row in the matrix A B sums to 2.
−1 −1 1
(iii) Every row in the matrix A B sums to .
2

Which of the above statements is/are true?

(a) None of the statements (i), (ii), (iii) is true.

(b) All the three statements (i), (ii), and (iii) are true. ✓
(c) Statement (i) is true but not necessarily statements (ii) or (iii).

(d) Statements (i) and (ii) are true but not necessarily statement (iii).

(e) Statements (i) and (iii) are true but not necessarily statement (ii).

15. Suppose Michelle gives Asna and Badri two dierent numbers from N = {1, 2, 3, . . .}.
It is commonly known to both Asna and Badri that they each know only their own
number and that it is dierent from the other one. The following conversation ensues.

Michelle: I privately gave each of you a dierent natural number. Which of you has the
larger of the two numbers?
Asna: I don't know.
Badri: I don't know either.
Asna: Oh, then I know who has the larger number.
Badri: In that case, I know both numbers. What numbers were Asna and Badri
respectively given?

(a) Asna was given 2, Badri was given 3. ✓
(b) Asna was given 3, Badri was given 2.

(c) Asna was given 3, Badri was given 4.

(d) Asna was given 4, Badri was given 3.

(e) None of the above.

GS 2024 CS Section: Solutions Page 6 of 11

CS Section
1. Consider the following three functions de
ned for all positive integers n ≥ 0.

f (n) = | sin(n) + n|,
g(n) = n,
h(n) = | sin(n)| .

Which of the following statements about these functions is / are true?

(i) f (n) = O(g(n))
(ii) g(n) = O(f (n))
(iii) h(n) = O(g(n))

(a) Only (i) is true.

(b) Only (ii) is true.

(c) Only (i) and (ii) are true.

(d) Only (ii) and (iii) are true.

(e) All of (i), (ii), and (iii) are true. ✓

2. Let S be the set of all 4-digit numbers created using just the digits 1, 2, 3, 4, 5 such
that no two successive digits are the same. If the numbers in S are arranged in
ascending order, what is the 100th number in this sequence?

(a) 2135

(b) 2324

(c) 2315

(d) 2352

(e) 2415 ✓

3. For any positive integer N , let p(N ) be the probability that a uniformly random
number a ∈ {1, . . . , N } has an odd number of factors (including 1 and the number
itself ).

Which of the following is true about the function p : N → R?

(a) limN →∞ p(N ) = 12 .
log N


(b) p(N ) = Θ .
N
1


(c) p(N ) = Θ .
N
 
(d) p(N ) = Θ √1N . ✓
 
1
(e) p(N ) = Θ .
log N

GS 2024 CS Section: Solutions Page 7 of 11

4. Consider functions f and g from the set of positive real numbers to itself, recursively
de
ned as follows.

∀n ≤ 1 f (n), g(n) = 1,
∀n > 1 f (n) = 3f (n/3) + n2 ,
∀n > 1 g(n) = n2/3 g(n1/3 ) + n.
Which of the following options is correct about their asymptotic behaviour?

(a) f (n) = Θ(n2 ) and g(n) = Θ(n log log n) ✓
(b) f (n) = Θ(n2 ) and g(n) = Θ(n log n)
(c) f (n) = Θ(n2 log n) and g(n) = Θ(n log log log n)
(d) f (n) = Θ(n2 log n) and g(n) = Θ(n log log n)
(e) f (n) = Θ(n2 log n) and g(n) = Θ(n log n)

5. For two languages A, B over the alphabet Σ, let the perfect shue of A and B be
the language

 
w = a1 b1 a2 b2 · · · ak bk where a1 a2 · · · ak ∈ A and b1 b2 · · · bk ∈ B
w : .
and k ∈ N

Consider the following statements.

(i) If A and B are regular, then perfect shue of A and B is regular.

(ii) If A and B are regular, then perfect shue of A and B is context-free.

(iii) If A and B are decidable, then perfect shue of A and B is decidable.

Which of above statements is/are true?

(a) All of (i), (ii) and (iii). ✓
(b) Only (i) and (ii).

(c) Only (ii).

(d) Only (ii) and (iii).

(e) None of (i), (ii), (iii) is true.

6. The four nucleotides in DNA are called A, C, G, and T. Consider the following
languages over the alphabet {A, C, G, and T}.

L1 = {(AC)n (GT)n | n ≥ 0}
L2 = {An Cn Gn Tn | n ≥ 0}
L3 = {(AT)n (CG)m | m ̸= n and m, n ≥ 0}

Which of the above languages is/are context-free?

(a) Only L1 .

(b) Only L3 .

(c) Only L1 and L3 . ✓

GS 2024 CS Section: Solutions Page 8 of 11

(d) Only L1 and L2 .

(e) All three of L1 , L2 , L3 .

7. Consider the following algorithm that takes as input a positive integer n.

if (n == 1) {
return "Neither prime nor composite."
}
m = 2
while (m < n) {
if (m divides n) {
return "Composite."
}
m = m+1
}
return "Prime."

2 3 4
If n is a number of the form n = p q r where p, q, r are natural numbers greater
than 1, how many times does the while loop in the algorithm run?

In the options below, for any real number m, ⌈m⌉ denotes the least integer greater
than or equal to m.

(a) The while loop runs at most ⌈n1/9 ⌉ times for all natural numbers
p, q, r greater than one. ✓
1/9
(b) The while loop runs at most ⌈n ⌉ times only if p, q, r are all distinct.
1/9
(c) The while loop runs at most ⌈n ⌉ times only if at least two of p, q, r are
distinct.
1/9
(d) The while loop runs at most ⌈n ⌉ times only if p, q, r are distinct primes.
1/9
(e) The while loop runs at most ⌈n ⌉ times only if p, q, r are distinct primes
or distinct prime powers.

8. In the following pseudocode, assume that for any pair of integers x ≤ y , the function
random (x , y) produces an integer uniformly chosen from the set {x, x + 1, . . . , y}.

n = 9
for (i = 1 to n) {
A[i] = i
}
for (i = 1 to n) {
r = random (i , n)
temp = A[i]
A[i] = A[r]
A[r] = temp
print A[i]
}

GS 2024 CS Section: Solutions Page 9 of 11

Which of the following statements is TRUE of the output of the code?

(a) It outputs all permutations of 123456789 with equal probability.
✓
(b) It never outputs 123456789.

(c) It outputs all cyclic permutations of 123456789 with equal probability, and
does not print any other output.

(d) The output is always 987654321.

(e) The output may not be a permutation of 123456789.

9. Given m vectors ⃗
x1 , ⃗x2 , . . . , ⃗xm in Rd , we construct an undirected graph G = (V, E) as
follows. Each vector ⃗
xi is represented by a vertex vi . We add an edge between vertices
vi and vj if the corresponding pair of vectors ⃗xi and ⃗xj are linearly independent.
Which of the following statements regarding the graph G must be TRUE, for any
x1 , ⃗x2 , . . . , ⃗xm ? Recall that a clique in a graph is a set of vertices S ⊆ V
such vectors ⃗
that have an edge between every pair of vertices in S .

(a) If m > d, the graph must be disconnected.

(b) Any clique has size at most d

(c) Any clique has size at most m/2

(d) The maximum degree of any vertex in G is at most d

(e) None of the above ✓

10. Arun has a non-empty subset S of the numbers {1, 2, 3, . . . , 1000}. Bela wants to

nd any number x in Arun's set S .

To do this, Arun and Bela decide to play a game which proceeds in rounds. In each
round, Bela can give Arun a subset T ⊆ {1, 2, 3, . . . , 1000}, and Arun answers with
a YES if S ∩ T is non-empty, and with NO otherwise.

In the worst case, how many rounds will Bela need to
nd out some x in Arun's set
S?
(a) 9

(b) 10 ✓
(c) 11

(d) 1023

(e) 1024

11. Let C denote the set of complex numbers and let k be a positive integer. Given a
non-zero univariate polynomial f (x) with coe
cients in C and an a ∈ C, we say that
k
a is a zero of f of multiplicity k if f (a) = 0, ddxfk (a) ̸= 0, and for all i ∈ {1, . . . , k − 1},
di f
dxi
(a) = 0.
Which of the following is true for every polynomial f of degree d and every positive
integer k ?

GS 2024 CS Section: Solutions Page 10 of 11

(a) The number of distinct zeroes in C of f of multiplicity k is at most
d/k , and can be smaller than d/k as well. ✓
(b) The number of distinct zeroes in C of f of multiplicity k is at least d/k ,
and can be larger than d/k as well.

(c) The number of distinct zeroes in C of f of multiplicity k is equal to d/k .

(d) The number of distinct zeroes in C of f of multiplicity k is at least d, and
can be larger than d as well.

(e) The number of distinct zeroes in C of f of multiplicity k is equal to d.

12. In the n-queens completion problem, the input is an n × n chess board with queens
on some squares, and the goal is to determine if there is a way to place more queens
so that the total number of queens is n and no two queens attack each other (two
queens are said to attack each other if they are on the same row, or they are on the
same column, or they are on the same diagonal).

Consider the following statements:

(i) The n-queens completion problem is decidable.
n

(ii) The n-queens completion problem is decidable in time O nn .

(iii) The problem of checking whether a given program solves the n-queens comple-
tion problem is decidable.

(iv) The problem of checking whether a given program solves the n-queens comple-
nn


tion problem in time O n  is decidable.

(v) The problem of checking whether a given program solves the n-queens comple-
nn


tion problem is decidable in time O n .

Which of the above is true?

(a) Only (i) and (ii).

(b) Only (i) and (iii).

(c) Only (i), (ii) and (iv). ✓
(d) Only (iii),(iv) and (v).

(e) Only (i), (iii) and (iv).

13. Suppose we are given a graph G = (V, E) with non-negative edge weights {we }e∈E .
Consider the following problems:

P1: Finding a minimum spanning tree of G.

P2: Finding a maximum spanning tree of G.

P3: Finding a cycle of smallest weight in G.

P4: Finding a cycle of largest weight in G.

Note: a cycle consists of distinct vertices.

Assuming P ̸= NP, which of the above problems can be solved in polynomial time?

GS 2024 CS Section: Solutions Page 11 of 11

(a) P1, P2 but not P3, P4.

(b) P1, P3 but not P2, P4.

(c) P1 but not P2,P3, P4.

(d) P1,P2,P3 but not P4. ✓
(e) P1, P4 but not P2, P3.

14. For an undirected graph G, let G refer to the complement (a graph on the same
vertex set as G, with (i, j) as an edge in G if and only if it is not an edge in G).
Consider the following statements.

(i) G has a vertex-cover of size at most k .
(ii) G has an independent set of size at least k .
(iii) G has an independent set of size at least n − k .
(iv) G has a clique of size at least k .
(v) G has a clique of size at least n − k .

Which of the following is true for any graph G and its complement graph G?

(a) (i) is equivalent to (iii) and (iv).

(b) (i) is equivalent to (iii) and (v). ✓
(c) (i) is equivalent to (ii) and (iv).

(d) (i) is equivalent to (ii) and (v)

(e) None of the
ve statements are equivalent to each other.

15. Consider the following automata:

0 0,1

1
1

0

Let N be the number of 0/1-strings of length exactly 6 accepted by this automata.
Which of the following is true about N ?

(a) N ≤ 4.
(b) 4 < N ≤ 8.
(c) 8 < N ≤ 16.
(d) 16 < N ≤ 32. ✓
(e) 32 < N ≤ 64.