TIFR GS 2023 Question Paper Computer Science

GS 2023 Computer and Systems Sciences: Solutions Page 1 of 16

Common Section
1. Let A be a symmetric 3 × 3 matrix with real entries. Let u and v be non-zero vectors
with real entries such that Au = 2u and Av = 3v. From the set of values {0, 1, −1},
which values can the inner product uT v take?
(a) 0 only ✓
(b) 1 only
(c) −1 only
(d) All of the values 0, 1 and −1
(e) None of the values 0, 1 and −1

2. How many distinct rectangles can be formed using the vertices in the grid shown
below? Squares are also counted as rectangles, and two rectangles are distinct if
either their top-left vertices are different or their bottom-right vertices are different.

(a) 16
(b) 25
(c) 36
(d) 64
(e) 100 ✓

3. A is an n × n matrix with real-valued entries. Further, there exists a vector x ̸= 0
such that Ax = 0. Now consider a given vector b in Rn . How many possible vectors
z exist, so that Az = b?
(a) 0
(b) 1
(c) n − 1
(d) n
(e) Either 0 or infinite ✓

4. Let R be the set of all real numbers. Consider the relation T defined as

T = {(x, y) ∈ R × R such that 4 + xy > 0}.

GS 2023 Computer and Systems Sciences: Solutions Page 2 of 16

(Recall that a relation S ⊆ R × R is said to be reflexive if for all x, (x, x) ∈ S, and
symmetric if whenever (x, y) ∈ S, it is also the case that (y, x) ∈ S. It is said to be
transitive if whenever (x, y) ∈ S and (y, z) ∈ S, it is also the case that (x, z) ∈ S.
A relation is said to be an equivalence relation if it is symmetric, transitive, and
reflexive.)
Then, the relation T is
(a) reflexive and transitive but not symmetric
(b) an equivalence relation
(c) reflexive and symmetric but not transitive ✓
(d) symmetric but not reflexive and not transitive
(e) symmetric and transitive but not reflexive

5. Suppose A is a 2 × 2 matrix such that the sum of the principal diagonal entries of A
is 10 and the sum of the principal diagonal entries of A2 is 20. (For any 2 × 2 matrix
B, the principal diagonal entries of B are the entries B1,1 and B2,2 .) What is det(A)?
(a) 0
(b) 40 ✓
(c) 80
(d) Nonzero, but cannot be uniquely determined from the above data.
(e) Cannot be uniquely determined from the above data, and could also be zero.

6. For a function f : R → R, consider the following conditions.

(C1) |f (x)| ≤ |x| for all x ∈ R.
(C2) |f (x)| ≤ |x|2 for all x ∈ R.
(C3) |f (x)| ≤ |x|3 for all x ∈ R.

Which of the above conditions imply that f is differentiable at 0?
(a) Condition (C1) only
(b) Condition (C2) only
(c) Condition (C3) only
(d) Conditions (C1) and (C2) only
(e) Conditions (C2) and (C3) only ✓

7. Suppose f (x) is a polynomial of the form ax2 + bx + c, with a, b, c unknown real
numbers. Suppose you are additionally told that f (1) = 2 and f (−1) = 3. Consider
the following four statements.

(S1) f (0) cannot be determined from the given data.
(S2) f (2) cannot be determined from the given data.
(S3) Both f (0) and f (2) can be determined from the given data.

GS 2023 Computer and Systems Sciences: Solutions Page 3 of 16

(S4) f (0) and f (2) satisfy 3f (0) + f (2) = 9.

Which of the above statements are true?
(a) Statements (S1) and (S2) only
(b) Statements (S1), (S2), and (S4) only ✓
(c) Statement (S3) only
(d) Statements (S3) and (S4) only
(e) All four statements are true

8. Let µ be a probability distribution on the interval [0, 1] with probability density
function p(x) = c · x2 where c is an undetermined constant. Consider an interval
A = [a, b], with 0 ≤ a < b ≤ 1 such that
Zb
1
Pr [X ∈ A] = p(x)dx = .
X∼µ 2
a

Then, the smallest possible value of b − a is
1
(a) 1 − 21/3 ✓
(b) 21/3
1

(c) 1 − 21/2
1

(d) 21/2
1

(e) The smallest possible value of b − a cannot be determined uniquely from the
information given in the question.

9. Let S be the value of following infinite series:
∞
X 1
.
n=1
n4

In which of the following intervals must S lie?
h 4 4i
(a) 900
π π
, 450
(b) [0.95, 1.05]
h 4 4i
π
(c) 100 , π80 ✓
h 4 i
(d) 2 , π
π 4

(e) The series diverges, so S must be infinity.

10. Let Q be a set with n elements. Consider a system with states of the form (S, R)
where S ⊆ Q and R ⊆ Q, with the further restriction that R ⊆ S. Note that (∅, ∅) is
also a valid state of the system (here ∅ denotes the empty set). How many possible
states does the system have?
(a) 3n ✓

GS 2023 Computer and Systems Sciences: Solutions Page 4 of 16

(b) 2n
(c) 4n
(d) n3
(e) n3



11. We are given a set S = {x1 , . . . , xn } of distinct positive integers such that gcd(xi , xj ) =
1 for any i, j ∈ {1, . . . , n} where i ̸= j. What is the total number of invertible 2 × 2
matrices whose entries are distinct elements from the set S?
(Note: For positive integers a and b, gcd(a, b) denotes the greatest common divisor
of a and b.)
(a) n4
(b) (n − 1)4
(c) n2 (n − 1)2 /4
(d) n(n − 1)(n − 2)(n − 3) ✓
(e) n(n − 1)(n − 2)(n − 3)/4!

†
12. Suppose is a piece on a chess board that attacks squares that are exactly two
steps in the vertical direction, and squares that are adjacent horizontally (as marked
with a “ ⋆” figure in the image below)

⋆

⋆ † ⋆

⋆

What is the maximum number of these pieces that can be placed on the squares of a
standard 8 × 8 chess board such that no two of these pieces attack each other? (Note
that each square is allowed to contain at most one piece.)
(a) 4
(b) 8

GS 2023 Computer and Systems Sciences: Solutions Page 5 of 16

(c) 16
(d) 24
(e) 32 ✓
13. We have a coin that is equally likely to land heads (denoted ‘H’) or tails (denoted
‘T’) when tossed. Suppose we keep tossing this coin and stop the game as soon as
we see three successive tosses giving either the sequence HTH or the sequence HHT.
What is the probability that when we stop the game, the last three successive tosses
are HHT?
(a) 1/4
(b) 2/3 ✓
(c) 3/4
(d) 1/3
(e) 1/2
14. Let f (x) = ax3 + bx2 + cx + d be a polynomial, where a, b, c, d are unknown real
numbers. It is further given that f (1) = 1, f (2) = 2, f (3) = 9, and f ′ (1) = 0. Then,
the value of f ′ (2) must be
(a) 1
(b) 2
(c) 3 ✓
(d) 4
(e) f ′ (2) cannot be determined uniquely from the information given in the question.
15. Consider the n × n matrix M defined as follows:
 
1 2 ... n

 n + 1 n + 2 . . . 2n 
 2n + 1 2n + 2 . . . 3n
M = .
.. .. .. 
. . ... . 


(n − 1)n + 1 (n − 1)n + 2 . . . n2
Let Mi,j denote the entry present in the i-th row and the j-th column of M for each
1 ≤ i, j ≤ n. Define a set S as
S = {Mi1 ,j1 + Mi2 ,j2 + · · · + Min ,jn | (i1 , . . . , in ) and (j1 , . . . , jn )
are permutations of [n]}.
(Here, [n] denotes the set {1, 2, . . . , n} of positive integers from 1 to n.) How many
elements does S have?
(a) 1 ✓
(b) n2



(c) n!
(d) (n!)2
(e) n

GS 2023 Computer and Systems Sciences: Solutions Page 6 of 16

Computer Science Section
1. Consider the following two statements:

• (P) The current population of Bhutan is greater than the current population of
India.
• (Q) The Moon is smaller than the Earth.

Clearly, (P) is false, while (Q) is true. Which of the following logical statements
evaluates to true?
(a) ¬P ⇒ Q ✓
(b) Q ⇒ P
(c) ¬(P ⇒ Q)
(d) P ⇔ Q
(e) None of the above

2. Which of the following is true about the set of regular languages and the set of
recursively enumerable languages over a finite alphabet Σ?
(a) The set of regular languages is countable while the set of recursively enumerable
languages is uncountable.
(b) The set of regular languages is uncountable while the set of recursively enumerable
languages is countable.
(c) The set of regular languages and the set of recursively enumerable
languages are both countable. ✓
(d) The set of regular languages and the set of recursively enumerable languages are
both uncountable.
(e) The set of regular languages is countable while whether the set of recursively
enumerable languages is countable or not is not known and is a longstanding
open problem.

3. Given a set F of intervals (si , ti )ni=1 on the integer line (assume all si , ti are distinct),
a subset S of F is said to be independent if no two intervals in S have a non-empty
intersection.
Consider greedy algorithms of the following type:
1 Order the intervals in F according to an ordering σ (soon to be specified).
2 S←∅; // ∅ denotes the empty set.
3 for I in F (in the order specified by σ) do
4 if I does not intersect any of the intervals already present in S then
5 S ← S ∪ {I}
6 return S
Here are three possible choices for the ordering σ:

GS 2023 Computer and Systems Sciences: Solutions Page 7 of 16

(C1) σ arranges the intervals in F in increasing order of si .
(C2) σ arranges the intervals in F in increasing order of ti .
(C3) σ arranges the intervals in F in increasing order of |si − ti |.

For which of these choices of the ordering σ does the algorithm always produce an
independent set of F of maximum size?
(a) Choice (C1) only
(b) Choice (C2) only ✓
(c) Choice (C3) only
(d) Choices (C2) and (C3), but not choice (C1)
(e) Choices (C1) and (C2), but not choice (C3)

4. Amar, Balu, and Chhaya are three friends and they play the following game. Chhaya
first chooses a number k ∈ U where U = {1, 2, . . . , 127}. She either gives k to both
Amar and Balu, or else she gives k to Amar and k + 1 to Balu. Amar computes
a function f : U → {0, 1}n on the number he receives from Chhaya and sends the
output of this function to Balu. Using this output and his own input, Balu has
to decide whether Chhaya gave the same number to Amar and him, or if she gave
numbers that differed by 1. What is the minimal n that allows Balu to distinguish
between these two cases?
(a) 1 ✓
(b) 2
(c) 7
(d) 127
(e) 128

5. Consider unit vectors a and b in Rn . Let w be an arbitrary vector in Rn and η be a
positive real number such that

aT b ≥ η > 0 ≥ wT b.

Define z = w + b. Consider the following statements.

(S1) zT a ≥ aT w + η
(S2) ∥z∥2 ≤ ∥w∥2 + 1
(S3) zT b ≥ 0

Choose the correct option from those below.
(a) Statements (S1), (S2), and (S3) are all true.
(b) Statements (S1) and (S2) must be true, but statement (S3) must be false.
(c) Statements (S1) and (S2) must be true, but statement (S3) may be
either true or false. ✓

GS 2023 Computer and Systems Sciences: Solutions Page 8 of 16

(d) Statements (S1) and (S3) must be true, but statement (S2) may be false.
(e) Statement (S1) may be false.
6. What is the solution to the following recurrence?
(
1 if n ≤ 10,
T (n) = √ √
n · T ( n) + n if n > 10.

(a) T (n) = Θ(n2 )
(b) T (n) = Θ(n log n)
√
(c) T (n) = Θ(n log n)
(d) T (n) = Θ(n log log n) ✓
(e) None of the above
7. Consider the random variables N, H, and T sampled as follows. First, N is sampled
from the Poisson(10) distribution. This means that for each integer n ≥ 0,
e−10 10n
Pr[N = n] = .
n!
Then N independent fair coins are tossed. H is then the number of heads, and T
the number of tails, obtained in this process. Choose the correct statement from the
ones given below.
(Note: Recall that for any real number x, ex is defined by the infinite series
∞
x
X xk
e = ,
k=0
k!

where 0! = 1 by convention.)
(a) H and T are independent and the variance of H is equal to the variance of N .
(b) H and T are independent and the variance of H is half the variance of
N. ✓
(c) H and T are not independent, but they are independent conditioned on N .
(d) H and T are not independent, and E[HT ] < E[H] × E[T ].
(e) H and T are not independent, and E[HT ] > E[H] × E[T ].
8. Let U be a finite set and let h be a function mapping U × U to U . Consider the
following process that assigns values to all nodes of a complete binary tree with 128
leaves. Initially, the leaf nodes are assigned arbitrary values from U . Then, the value
that is assigned to an internal node is the output of h on the values assigned to this
node’s children. The value of the tree is given by the value assigned to the root.
Once you have computed the value of the tree, you realize that the initial value that
was assigned to the 53rd leaf was incorrect and you therefore need to use a different
value for the 53rd leaf. Given this incorrect tree as input, at most how many times
would an optimal algorithm need to recompute h in order to obtain the correct value
of the tree?

GS 2023 Computer and Systems Sciences: Solutions Page 9 of 16

(a) 7 ✓
(b) 8
(c) 53
(d) 127
(e) 255

9. Fix a positive integer n, and let n = pe11 pe22 · · · pekk be the prime factorization of n.
Here, p1 , . . . , pk are prime numbers and ei ≥ 1 for all 1 ≤ i ≤ k. Call a sequence
(n0 , n1 , . . . , nt ) where n0 = n and nt = 1 relevant if for every 0 ≤ i ≤ t − 1, the
number ni /ni+1 is a prime number. What is the total number of relevant sequences?
(a) (p1 + 1) × (p2 + 1) × · · · × (pk + 1)
(b) (p1 + 1)e1 × (p2 + 1)e2 × · · · × (pk + 1)ek
(c) (e1 + e2 + · · · + ek )!
(d) (e1(e!)×(e
1 +e2 +···+ek )!
2 !)×···×(ek !)
✓
(e) None of the above

10. A d-regular graph is one in which every vertex has degree d. Also, a minimum cut
in a graph is a smallest set of edges which, upon removal, disconnects the graph, so
that there are vertices in the resulting graph with no path between them. We are
given two graphs. G1 = (V1 , E1 ) is a connected, 3-regular graph. G2 = (V2 , E2 ) is a
connected, 4-regular graph. The vertex sets V1 and V2 are disjoint. We are further
told that the size of any minimum cut in G1 is the same as the size of any minimum
cut in G2 . Which of the following must be the size of this minimum cut?
(a) 0
(b) 1
(c) 2 ✓
(d) 3
(e) 4

11. Let m = 2877426671. It is known that p = 5754853343 = 2m + 1 is a 10-digit prime
number. What is 16m (mod p)?
(a) 1 ✓
(b) 4
(c) 16
(d) 2877426671
(e) 5754853342 (which is actually −1 (mod p))

12. A graph G = (V, E) is said to be k-colourable if the set V of vertices can be coloured
with k colours such that no edge has both its endpoints of the same colour. It is
known that the following language 3COL is NP-complete.

3COL = {G | G is 3-colourable}.

GS 2023 Computer and Systems Sciences: Solutions Page 10 of 16

Consider the following algorithmic problems (assume that the input graph G is pro-
vided as its adjacency matrix):
(P1) Given a graph G as input, check if G is 2-colourable.
(P2) Given a graph G as input, find the minimum value of k such that G is k-
colourable.
(P3) Given a graph G, check if G is 3-colourable.
(P4) Given a graph G, along with a guarantee that the minimum value of k such that
G is k-colourable is either 2 or 3, decide which of the two is the case.
Assume NP ̸= P. Then, which of the above problems can be solved in polynomial
time?
(a) Only problem (P1)
(b) Only problems (P1) and (P4) ✓
(c) Only problems (P2) and (P3)
(d) Only problems (P1), (P3) and (P4)
(e) Only problems (P1), (P2) and (P4)
13. You have a regular tetrahedron and 4 distinct colours. You wish to paint the faces
of the tetrahedron such that each face gets a different colour. How many ways can
you colour the tetrahedron? Recall that a regular tetrahedron is a three-dimensional
solid with exactly four faces, all of which are equilateral triangles: see the sketch
given below (not drawn to scale) for a rough view of such a solid. Two colourings of
the tetrahedron are considered the same if they are identical after possibly rotating
the tetrahedron.

(a) 24
(b) 12
(c) 8
(d) 6
(e) 2 ✓
14. A k-term T = ℓ1 ∧ ℓ2 ∧ · · · ∧ ℓr is defined to be a conjunction of at most k literals,
where each literal ℓi is a Boolean variable or its negation and r ≤ k. A formula
Φ is said to be a k-DNF if it is of the form T1 ∨ T2 ∨ . . . · · · ∨ Tm where each Ti
is a k-term. An assignment of True/False values to the variables appearing in a
formula Φ is said to be a satisfying assignment for Φ if, under the assignment, Φ
evaluates to True. Otherwise, the assignment is said to be a violating assignment
for Φ. Consider the following statements

GS 2023 Computer and Systems Sciences: Solutions Page 11 of 16

(S1) Given a 2-DNF Φ, one can find a violating assignment for Φ in polynomial time.
(S2) It is NP-hard to find a violating assignment for a given 3-DNF Φ.
(S3) Given a 3-DNF Φ, one can find a satisfying assignment for Φ in polynomial
time.

Which of the following statements are correct?
(a) Statements (S1), (S2), and (S3) are all true. ✓
(b) Statements (S1) and (S2) are true, but statement (S3) is not known to be true.
(c) Statements (S2) is true, but statements (S1) and (S3) are not known to be true.
(d) Statements (S1), (S2), and (S3) are false.
(e) Statements (S1) and (S3) are true, but (S2) is not known to be true.

15. Consider the language L = {ai $aj $bk $ | k ⩽ max(i, j), i, j, k ≥ 0} over the alphabet
Σ = {a, b, $}. The complement of the language L, that is, Σ∗ \ L is denoted by L.
Which of the following is true?
(a) Both L and L are regular languages.
(b) L is a context-free language and L is a regular language.
(c) Both L and L are context-free languages.
(d) L is a context-free language and L is not a context-free language. ✓
(e) Neither is L a context-free language nor is L a context-free language.

GS 2023 Computer and Systems Sciences: Solutions Page 12 of 16

Systems Science Section
1. Consider a fair coin with probability of heads and tails equal to 1/2. Moreover
consider two dice, first D1 that has three faces numbered 1, 3, 5 and second D2 that
has three faces numbered 2, 4, 6. When rolled, for both D1 and D2 , each of the three
faces are equally likely.
A random experiment is conducted as follows. First, the coin is flipped once. If it
shows heads, dice D1 is rolled once, while if the coin shows tails, D2 is rolled once,
and the experiment ends.
Let X be the (random) number seen on the rolled dice in the experiment.
What is E[X] ?
(a) 27 ✓
(b) 4
(c) 3
(d) 29
(e) None of the above

2.
a⋆ = max x2 + y 2 − 8x + 7
x,y
s.t. x2 + y 2 ≤ 1
y≥0
Then a⋆ is
(a) 16 ✓
(b) 14
(c) 12
(d) 10
(e) None of the above

3. Let

P = {(x, y) : x + y ≥ 1, 2x + y ≥ 2, x + 2y ≥ 2, (x − 1)2 + (y − 1)2 ≤ 1}.

Compute
min 2x + 3y.
(x,y)∈P

(a) 2
(b) 3
(c) 4
(d) 6
(e) None of the above ✓

GS 2023 Computer and Systems Sciences: Solutions Page 13 of 16

4. Recall that the entropy (in bits) of a random variable X which takes values in N, the
set of natural numbers, is defined as
∞
X 1
H(X) = pn log2 ,
n=1
pn

where, for n ∈ N, pn denotes the probability that X = n.
Consider a fair coin (i.e., both sides have equal probability of appearing). Suppose we
toss the coin repeatedly until both sides are observed. Let X be the random variable
which denotes the number of tosses made. What is the entropy of X in bits?
(a) 1
(b) 2 ✓
(c) 4
(d) Infinity
(e) None of the above

5. Let B denote the unit ball in R2 , and Q a square of side length 2. Let K be the set
of all vectors z such that for some x ∈ B and some y ∈ Q, z = x + y. The area of K
is
(a) 4 + π
(b) 6 + π
(c) 8 + π
(d) 10 + π
(e) 12 + π ✓

6. An ant in the plane travels in a spiral such that its position (x(t), y(t)) at time t ≥ 0
is (et cos t, et sin t). At time t = 1, find the real part of ln (x(t) + iy(t)) .
(a) −2
(b) 1 ✓
(c) 0
(d) −1
(e) 2

7. Let f (x) be a positive continuous function on the real line that is the
R ∞density of a ran-
dom variable X. The differential entropy of X is defined to be − −∞ f (x) ln f (x)dx.
In which case does X have the least differential entropy? You may use √ these facts:
The differential entropy for a Gaussian with standard deviation σ is ln(σ 2πe). The
differential entropy of an exponential with mean λ−1 is 1 + ln(λ−1 ).
(a) f (x) := (1/2)e−|x| .
√
(b) f (x) := ( 100π)−1 exp(−|x|2 /100).
√
(c) f (x) := ( 20π)−1 exp(−|x|2 /20).

GS 2023 Computer and Systems Sciences: Solutions Page 14 of 16

(d) f (x) := (1/4)e−|x|/2 .
(e) f (x) := e−2|x| . ✓

8. Suppose a bag contains 5 red balls, 3 blue balls, and 2 black balls. Balls are drawn
without replacement until the bag is empty. Let Xi be a random variable which
takes value 1 if the i-th ball drawn is red, value 2 if that ball is blue, and 3 if it is
black. Let the joint probability mass function of the random variables be denoted
by PX1 ,X2 ,...,X10 . Consider the following statements, where we write f = g for two
functions f and g defined on the same domain to mean that, for all possible elements
in the domain, both functions map the same element to the same value (i.e., we write
f = g if f (y) = g(y) for all y in the domain):

(i) PX1 = PX10
(ii) PX1 ,X10 = PX10 ,X1
(iii) PX1 ,X2 ,X3 = PX3 ,X7 ,X5
(a) Only (i)
(b) Only (i) and (ii)
(c) Only (i) and (iii)
(d) All of (i), (ii), and (iii) ✓
(e) None of (i), (ii), or (iii)

9. Consider an n × n matrix A with the property that each element of A is non-negative
and the sum of elements of each row is 1.
Consider the following statements.

1. 1 is an eigenvalue of A
2. The magnitude of any eigenvalue of A is at most 1
3. Eigenvalue of A can be negative

Then which of the following is TRUE ?
(a) Only statement 1 is correct
(b) Only statements 1 and 2 are correct
(c) Only statements 1 and 3 are correct
(d) Only statements 2 and 3 are correct
(e) All statements 1, 2, and 3 are correct ✓

10. Convolution between two functions f (t) and g(t) is defined as follows:
Z ∞
f (t) ∗ g(t) = f (τ )g(t − τ )dτ.
−∞

Let u(t) be the unit-step function, i.e., u(t) = 1 for t ≥ 0 and u(t) = 0 for t < 0.
What is f (t) ∗ g(t) if f (t) = exp(−t)u(t) and g(t) = sin(t)u(t)?

GS 2023 Computer and Systems Sciences: Solutions Page 15 of 16

(a) 12 (exp(−t) − sin(t) + cos(t)) u(t)
(b) 21 (exp(−t) + sin(t) − cos(t)) u(t) ✓
(c) 21 (exp(−t) + 2 sin(t) − cos(t)) u(t)
(d) 21 (exp(−t) + sin(t) − 2 cos(t)) u(t)
(e) 21 (exp(−t) − sin(t) + 2 cos(t)) u(t)

11. Consider the function
f (x) = xe|x| + 4x2
for values of x which lie in the interval [−1, 1]. In this domain, suppose the function
attains the minimum value at x∗ . Which of the following is true?
(a) −1 ≤ x∗ < −0.5
(b) −0.5 ≤ x∗ < 0 ✓
(c) x∗ = 0
(d) 0 < x∗ ≤ 0.5
(e) 0.5 < x∗ ≤ 1

12. Consider a disk D of radius 1 centered at the origin. Let X be a point uniformly
distributed on D and let the distance of X from the origin be R. Let A be the
(random) area of the disk with radius R centered at the origin. Then E[A] is
(a) π3
(b) π6
(c) π4
(d) π2 ✓
(e) None of the above

13. Let X be a random variable which takes values 1 and −1 with probability 1/2 each.
Suppose Y = X + N , where N is a random variable independent of X with the
following probability density function (p.d.f.):

1


c 1 − 2 n

 0≤n≤2
1
fN (n) = c 1 + 2 n −2 ≤ n < 0
otherwise

0


where c is such that the above is a p.d.f. Now consider a “detector” which tries to
guess X based on observing Y . Suppose the detector makes a decision
(
1 if Y ≥ λ
X̂ =
−1 if Y < λ

where λ is chosen such that the probability of making an incorrect decision, i.e.,
Pr(X̂ ̸= X), is minimized. What is this minimum probability of incorrect decision?
(a) 0

GS 2023 Computer and Systems Sciences: Solutions Page 16 of 16

(b) 1/8 ✓
(c) 1/4
(d) 1/2
(e) None of the above

14. Suppose that Z ∼ N (0, 1) is a Gaussian random variable with mean zero and vari-
ance 1. Let F (z) ≡ P(Z ≤ z) be the cumulative distribution function (CDF) of Z.
Define a new random variable Y as Y = F (Z). This means that the random variable
Y is obtained by evaluating the CDF F (·) at randomly chosen points. Then the value
of E Y is:


(a) F (1)
(b) 1
(c) 21 ✓
(d) √12π
(e) π4

15. Let {xn }n≥0 be a sequence of real numbers which satisfy

xn+1 (1 + xn+1 ) ≤ xn (1 + xn ), n ≥ 0.

Choose the correct option from the following.
(a) The sequence could be unbounded.
(b) The sequence is always bounded but does not necessarily converge. ✓
(c) The sequence always converges to a non-zero limit.
(d) The sequence always converges to zero.
(e) None of the above.