CMI Entrance Exam 2026 Question Paper Solution M.Sc or Ph.D in Computer Science

FOR CMI EXAM PREPARATION

CMI 2026
Question Paper
Solution · M.Sc or Ph.D
in Computer Science
EXAM YEAR TYPE

CMI 2026 Question Paper Solution
SUBJECT

M.Sc or Ph.D in Computer Science

Notes · Sample Papers · Previous Year Papers · Mock Tests

m
m .co

m .co s em
se g la
CHENNAI MATHEMATICAL aINSTITUTE
M.Sc. / Ph.D. Programme in Computer Science
Entrance Examination, 2026

Part A
1. Six people A, B, C, D, E, F sit around a circular table.
m
o
• A sits opposite D
c
m m .co
m . to A
• B is not adjacent
s e
• C sits s e l a
l a immediately
• Egis adjacent to D
to the right of B
ag
a
Who sits opposite C?
(a) B (b) D (c) E (d) F

Answer. (c)

Let there be six chairs around the table, numbered 0, 1, … , 6 clockwise. Suppose, without
m
.co
loss of generality, that A sits in chair 0. Then D has to sit in chair 3. Since B is not adjacent
to A, she has to sit in chair 2 or chair 4. C sits to the right of B, which means that either B
e m
and C sit in chairs 2 and 1, or they sit in chairs 4 and 3. But 3 is already occupied by D, so B
l as
⊣
and C are in 2 and 1. E is adjacent to D, so he has to be in chair 4, which is opposite to chair
1, on which sits C.
ag
2. Dhruva is attending a party. If they play both dumb charades and musical chairs, he will
leave the party. If Abhay does not dance or Bharat does not juggle, then also he will leave
the party. If Abhay dances and Bharat juggles, then everyone gets free chocolate. Suppose
Mahesh, who is also attending the party, did not get free chocolate and musical chairs were
played, which of the following can you infer?
(a) Dumb charades are not played (b) Abhay did not dance
m
.co
(c) Bharat did not juggle (d) Dhruva left the party
m
c. o Answer. (d)
s e m
e m l a
las a g
Let us use the following letters to denote various sentences of interest.
ag
• a: Abhay dances.
• b: Bharat juggles.
• c: Everyone gets free chocolate.
• d: Dhruva leaves the party midway.
• e: Dumb charades are not played.

m
• f : Musical chairs are not played.
.
.co s e m
s em 1
l a
g la ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 1 of 12

Also assuming the standard logical notation ¬, ∧, ∨ and → which stand for negation, con-
junction, disjunction and implication (respectively), we have the following facts.

(a ∧ b) → c
(2) (¬a ∨ ¬b) → d
(1)

d → (e ∨ f )
¬c
(3)

¬f
(4)
(5)

From (1) and (4), it follows that ¬a ∨ ¬b. From (2), it now follows that d. and So a is false
or b is false. So d (which is the same as option (d)) is true. One can check that each of the

⊣
other options (a), (b) and (c) can be false along with (d). So (d) is the only option that can be
inferred from the given information.

and exactly one correct answer. You know the answers to 80% of the questions, and you
3. Suppose you are writing a 100-question multiple-choice exam with 4 choices per question

guess the answer to the remaining 20% uniformly at random. What is the expected number
of questions you answer correctly?
(a) 82 (b) 85 (c) 90 (d) 95
(a) 82 (b) 85 (c) 90 (d) 95

Answer. (b)

You will anyway answer 80 questions correctly. Out of the remaining 20, you will get ⋅ 20
1

⊣
4
correct, which evaluates to 5.

4. In a multiple choice test with 100 questions, each question has 5 possible answers with ex-
actly one of them being correct. A student knows the answer to 40 of these questions. For
the rest he will guess the answer uniformly at random.
A question is picked uniformly at random and posed to the student. If he answers it cor-
rectly, what is the probability that he actually knew the answer to that question?
2 5 13 10
(a) (b) (c) (d)
5 13 25 13

Answer. (d)

Suppose a question picked uniformly at random and the students provides an answer. Let
K be the event that the student knows the answer. Clearly, Pr(K ) = = . Let C be the
40 2
100 5
event that the answer provided is correct.

Pr(C) = Pr(C ∣ K ) ⋅ Pr(K ) + Pr(C ∣ ¬K ) ⋅ Pr(¬K ) = 1 ⋅ + ⋅ = + = .
2 1 3 2 3 13
5 5 5 5 25 25
The question asks us to compute the probability that the student actually knows the answer,
provided that the answer was correct. This is
Pr(K ∧ C) Pr(K ) 2/5
Pr(K ∣ C) = = = 13 = ⋅ = . ⊣
Pr(C) Pr(C) /25
2 25 10
5 13 13

2

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 2 of 12

m
m .co

m .co s em
se g la
a are 50 questions, each worth
5. 1000 candidates appear in a competitive examination. There

Only 10 candidates scored 80 or above. Let ni (0 ⩽ i ⩽ 100) denote the number of candidates
2 marks. There is no partial credit, and each answer is awarded either 0 marks or 2 marks.

whose score is i. Which of the following scenarios are possible?

(a) n0 = 100.
(b) For all odd numbers i ∈ {0, … , 100}, ni = 0.
(c) For all i ∈ {0, … , 100}, ni < 25. m
(d) There are at most 30 values of i ∈ {0, … , 100} such that ni = 0.
m .co
.co s e m
s emand (b) l a
ag
(a)

g la
Sinceaeach question carries either 2 marks or 0 marks, (b) is always true (and therefore pos-

dates among 40 possible marks (all even numbers from 0 to 78). If ni < 25 for each of them,
sible). Since (b) holds, (d) is automatically false. Note that we have to distribute 990 candi-

it covers at most 960 candidates. Thus (c) is also false.
(a) is possible (though not necessary). Here is a possible distribution of the marks.

n0 = 100; n2 = 130; n2i+2 = 20 (1 ⩽ i ⩽ 38); n80 = 10; n2i+80 = 0 (1 ⩽ i ⩽ 10). ⊣

m
6. Let T (n) be the number of ways to tile a 3 × n rectangle with 1 × 2 dominoes; refer to the
figure for some examples for the case n = 4. m .co
s e
l a
3 ag
4 4 4 4

Four distinct tilings of a 3 × 4 rectangle with 1 × 2 dominoes.

Which of the following statements is/are true about the growth of T (n)?
m
m(a) T(2) = 3
c. o (b) m.co
m T (n) = 0 for all odd n. s e
s e la
(c) T (n) is given by a recurrence of the form T (n) = T (n − 1) + T (ng− 2).
g la (d) T (4) < 9.
a
a
Answer. (a) and (b)

• Option (a) is true. To see this, observe that a 3 × 2 rectangle can be tiled in 3 distinct
ways using 1 × 2 dominoes: (i) three horizontal dominoes; (ii) one horizontal domino
at the top and two vertical dominoes below; (iii) two vertical dominoes at the top and
m
one horizontal domino below. See the picture below:
.
.co s e m
s em 3
l a
g la ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 3 of 12

3

2

• Option (b) is true: Since each domino covers 2 squares, a 3 × n rectangle can only be
tiled if n is even. Thus T (n) = 0 for all odd n.
• Option (c) is false: If the recurrence T (n) = T (n − 1) + T (n − 2) held, then since T (1) = 0,
we would have T (3) = T (2) + T (1) = T (2). However, we know T (3) = 0 from option (b),
and T (2) = 3 from option (a).
• Option (d) is false. We know that T (2) = 3. It follows that there are at least 9 ways to
tile a 3 × 4 rectangle, by considering two disjoint 3 × 2 blocks. Hence T (4) ⩾ 9. ⊣

7. A binary string s of length 2026 starts with bit 0 and ends with bit 1. Let N00 , N01 , N10 , and
N11 denote the number of times that the sequences 00, 01, 10, and 11, respectively, appear
as pairs of adjacent bits in s. Which of the following equations are correct?
(a) N01 = N10 + 1 (b) N10 = N01 + 1
(c) N01 = 1013 − (N00 + N11 )/2 (d) N01 = 2026 − N00 − N11

Answer. (a) and (c)

The total number of adjacent pairs of bits in s is 2025, and so we have N00 + N01 + N10 +
N11 = 2025. Since the string begins with a 0 and ends with a 1, every transition from 1 to
0 must be—eventually—followed by a transition from 0 to 1. It follows that the number of

N01 = N10 + 1, and hence N10 = N01 − 1. Substituting, we get N00 + N01 +(N01 − 1)+ N11 = 2025,
0-to-1 transitions in s is exactly one more than the number of 1-to-0 transitions. That is:

N + N11
from which we get N01 = 1013 − 00 . ⊣
2

Questions 8 and 9 pertain to the pseudocode given below, which defines the function f (x ) (where x is as-
sumed to be a nonnegative integer). The code uses the function rem(n, d), which returns the remainder
after dividing n by d.

a←0
function f (x)

while x > 0 do
r ← rem(x , 2)
a ← (10 × a) + r
x ← (x − r )/2
end while
return a
end function

8. What is the value returned by f (43)?
(a) 101000 (b) 101011 (c) 110101 (d) 110100

4

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 4 of 12

m
m .co

m .co s e m
se g l a
Answer. (c) a
The sequence of values assumed by (a, x ) at the start of each iteration of the loop is given
below (in the execution of f (43)):

(0, 43) → (1, 21) → (11, 10) → (110, 5) → (1101, 2) → (11010, 1) → (110101, 0).

The loop is exited when x = 0, and 110101 is returned. ⊣
m
9. Which of the following best describes the running time of f (x )?
m .co
.co s e m
em
(a) Linear in x. (b) Quadratic in x.
s l a
ag
(c) Logarithmic in x. (d) Exponential in x.
g la
a (c)

At each iteration we replace x by ⌊ ⌋, and we stop when x = 0. So there can be at most log2 x
x

⊣
2
iterations.

10. Consider the following two procedures proc1 and proc2, which run in parallel after ini-
tializing x to 6 and y to 3. Running in parallel means that between any two lines of code

m
in one process, any number of lines of the other process may run. Both x and y are shared
variables which both processes can read/modify.
m .co
int x = 6, y = 3;

s e
l a
proc1

x
{

= 2*y;
ag proc2

y
{

= 2*x;

x = x - y; y = y - x;

} }

Which of the following values are possible for (x,y) after both processes have come to a
halt?
(a) (8,5) (b) (3,3) (c) (0,6) (d) (36,-12)
m
mAnswer. .co
.co em
(b), (c) and (d)

e m s
la4, there are six inter-
las Numbering the lines in proc1
as 1 and 2, and those in
g
as 3 and
a value of .
proc2

(x,y)

ag leavings possible. The table below lists them, along with the final

Interleaving 1234 1324 1342 3124 3142 3412
Value (3,3) (-6,18) (0,6) (12,0) (36,-12) (6,6)

Thus we see that (a) is not possible, while the other options are possible. ⊣

m .
.co s e m
s em 5
l a
g la ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 5 of 12

Part B
1. You are given a long sheet of (ruled) paper with the string MI written on the first line. You
are asked to fill in lines 2, 3, 4, … (in order) with other strings involving the letters M, I and
U, subject to the following rules, where x and y stand for any string (possibly empty) formed
using the letters M, I and U:

R1. If the previous line has Mx, you can write Mxx.
R2. If the previous line has xI, you can write xIU.
R3. If the previous line has xUUy, you can write xy.
R4. If the previous line has xIIIy, you can write xUy.

in is said to be derived. Here are two examples (where we write x1 → x2 → … xn−1 → xn to
You can stop at any line, at any point of time, and the string on the last line you have filled

mean that the lines 1, 2, … , n − 1, n have entries x1 , x2 , … , xn−1 , xn (in order).

E1. MI. (This shows that you can stop even without adding any line.)
E2. MI → MII → MIIII → MUI → MUIUI.
E3. MI → MII → MIIII → MIIIIU → MUIU.

Questions:

(a) For examples E2 and E3 above, write down which rule from R1 to R4 is used in each step.
(b) Show how to derive the strings MIUIU and MIUIUU. (Hint: To derive MIUIUU, first
derive MIIIIIIII (M followed by 8 occurrences of I) and then proceed.)
(c) Show that the string MIIMII cannot be derived.
(d) If x is any string derived using the rules above, and if n is the number of occurrences of
I in x, what are the possible values for n mod 3?
(e) Can the string MU be derived? If so, provide a derivation. If not, explain why not.

(a) The rules used in E2 are, in order, R1, R1, R4 and R1. The rules used in E3 are R1, R1, R2,
R1.
(b) For MIUIU, we have the derivation MI → MII → MIIII → MIU → MIUIU.
For MIUIUU, we have the derivation

MI → MII → MIIII → MIIIIIIII → MIIIIIIIIU → MIUIIIIU → MIUIUU.

(c) In every string derived from MI, the letter M occurs exactly once. So MIIMII cannot be
derived.
(d) n mod 3 is either 1 or 2. It starts with a value of 1, and rules R3 and R4 do not change its
value. R2 changes it from 1 to 2 and vice versa.
(e) MU has no occurrences of I, and hence cannot be derived, by the previous part. ⊣

6

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 6 of 12

m
m .co

m .co s em
se g la
2. For a set X, X denotes the set of all strings formed usinga
∗
X, including the empty string. By

that x is a prefix of y if there is some z ∈ X ∗ such that xz = y. Note that every x is a prefix of
xy, we mean the concatenation of x and y, i.e., the string x followed by the string y. We say

itself, and ε is a prefix of every x.
A function f ∶ Σ∗ → {0, 1}∗ is said to be a homomorphism if f (ε) = ε and f (xy) = f (x )f (y) for
all x , y ∈ Σ∗ . f is said to be prefix-free if f (a) is not a prefix of f (b) for any pair of distinct letters
a, b ∈ Σ. For example, if f (a) = 01 and f (b) = 101, then f (aba) = 0110101. For the following
questions, we assume that |Σ| = 8 and f ∶ Σ∗ → {0, 1}∗ is a prefix-free homomorphism. m
m
(a) Is it possible that f (a) is of length at most 3 for all a. If so, define such an f . If not,
.co
.co s e m
em
provide a proof that this is not possible.
s l a
l apossible that f (a) is of length 2 for some a ∈ Σ and f (b) is of length 3 for allabg∈
aΣg∖ {a}. If so, define such an f . If not, provide a proof that this is not possible.
(b) Is it

(c) Show that there are no distinct x , y ∈ Σ∗ such that f (x ) = f (y).

(a) We can map the 8 letters to 8 3-bit strings.
(b) Suppose, w.l.o.g., that f (a) = 01 for some a ∈ Σ. Then no b ∈ Σ can be mapped to the

length 3. Since |Σ| = 8, we have at least one b ∈ Σ ∖ {a} s.t. f (b) is not of length 3.
strings 000 or 001. So at most six elements of Σ can be mapped to binary strings of
m
.co
(c) This is proved by contradiction. Suppose that there exist distinct x , y such that f (x ) =
em
f (y). Let x = a1 … ak and y = b1 … bℓ for k, ℓ where each ai , bi ∈ Σ. One of the following
s
g la
cases holds:
a
(i) One of the strings is a proper prefix of the other.
(ii) There exists i ⩽ k, ℓ s.t. aj = bj for all j < i and ai ≠ bi .
For case (i), assume w.l.o.g. that x is a proper prefix of y. Then f (x ) has to be a proper
prefix of f (y), since otherwise we would have f (bk+1 ) = ⋯ = f (bℓ ) = ε, and no prefix-
free map can map a letter to ε, whenever |Σ| > 1.
For case (ii), since a1 … ai−1 = b1 … bi−1 , we have f (a1 … ai−1 ) = f (b1 … bi−1 ). This, along
with f (x ) = f (y), implies that f (ai … ak ) = f (bi … bℓ ). From this, it follows that eitherm
m f (ai = f (bi ) or one of f (ai ) and f (bi ) is a proper prefix of the other. In all cases, we have
.co
a violation of the prefix-freedom of f , since ai ≠ bi . ⊣
.co s e m
s em 3. Suppose G = (V , E) is a graph with |V | = 2k for some k ⩾ 1. Further, g l a suppose there is no
g la cycle of length 3 in G, i.e., G is triangle-free. Prove that |E| ⩽ k .a 2
a
Answer. Let u be a vertex of maximum degree, with deg(u) = d. There are 2k − d − 1
vertices in V ∖ (N (u) ∪ {u}). These vertices can contribute at most d(2k − d − 1) edges. By the
3-cycle free property, the vertices in N (u) have no edges between them. So the maximum
number of edges possible is d + d(2k − d − 1) = 2dk − d2 , which attains its maximum value
of d2 when d = k. ⊣

m .
.co s e m
s em 7
l a
g la ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 7 of 12

Part C
1. Consider a finite alphabet Σ = {0, 1}. For a string w ∈ Σ∗ , we write |w| for the length of w.
For u, v ∈ Σ∗ , we write u ⋅ v for the string obtained by concatenating u and v.
Let us define an operation πeven (w) inductively as follows:

πeven (ε) = ε
πeven (w) if |wa| is odd
∀w ∈ Σ∗ and ∀a ∈ Σ πeven (wa) = {
πeven (w) ⋅ a if |wa| is even

(a) What is πeven (001011)?
(b) For a language L ⊆ Σ∗ , define πeven (L) ∶= {πeven (w) ∣ w ∈ L}. What is πeven ((01)∗ )?
(c) Show that if L is regular, πeven (L) is also regular.

(a) 001. It is the projection on to the even positions of the word.
(b) πeven ((01)∗ ) = 1∗
(c) Let A = (Q , q0 , Σ, δ , F ) be a DFA accepting L. Construct an NFA (with ε-transitions)
B = (R, I, Σ, Δ, G) as follows:
• R = Q × {0, 1}
• I = {(q0 , 0)}
• Δ = {((q, 0), ε, (q′ , 1)), ((q, 1), a, (q′ , 0)) ∣ q, q′ ∈ Q , a ∈ Σ, δ (q, a) = q′ }
• G = F × {0, 1}
We can show that any run of A on w from q0 to f ∈ F can be mimicked by a run of B on
π(w), from (q0 , 0) to (f , i) ∈ G, where i = 0 if |w| is even, and i = 1 otherwise. Hence
for every word w accepted by A, the projection πeven (w) is accepted by B. Conversely,
for every accepting run of B, there exist letters that can replace ε appearing in the run

is on πeven (w). ⊣
by some letter of Σ, to make it a run of A. If w is the resulting word, then the run of B

2. Let Σ be a finite alphabet, and let L ⊆ Σ∗ . Two strings u and v in Σ∗ are said to be L-equivalent
if for all z ∈ Σ∗ , (uz ∈ L iff vz ∈ L).

(a) Consider Σ = {0, 1} and let L = 0∗ 1∗ 0∗ . For the following instances of u and v, explain
whether u and v are L-equivalent.
(i) u = 0, v = 1
(ii) u = 0, v = 00
(b) Let L be a regular language. Show that for any infinite set of strings S, there exist at
least two strings in S that are L-equivalent.

(a) (i) u = 0 is not L-equivalent to v = 1, since uz ∈ L and vz ∉ L for z = 010.

8

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 8 of 12

m
m .co

m .co s em
se g la
(ii) u = 0 is L-equivalent to v = 00. From the regular
a expression, we can see that
0z ∈ L iff 00z ∈ L for all z.
(b) Let A be a DFA accepting L. For any two words u, v, if the runs of A on them leads to the

⊣
same state, then u and v are L-equivalent. In an infinite set of strings S, at least two of
them will go to the same state of A, and hence will be L-equivalent.

3. You are given a graph on vertex set V = {a1 , … , ak } ∪ {b1 , … , bk }. The edge set is E = {(ai , bj ) ∣
i ≠ j}. An edge coloring of a graph is an assignment of colors to edges such that no two edges m
o m
sharing a common vertex receive the same color.
c m .co
m . s e
(a) Give an efficient
colors.se
algorithm to color the edges of the graph with minimum number
g
of
l a
l a a
ag many colors does your algorithm use?
(b) How

Answer. Each vertex in this graph has degree k − 1. Since all edges incident with any one
vertex must get different colours, any edge colouring of this graph requires at least k − 1
different colours.

(a) Go over the edges of the graph one by one. Give the colour (j − i) mod k to an edge of
the form (ai , bj ). Since every edge (ai , bj ) satisfies i ≠ j, these colours will be from the
set {1, 2, … , (k − 1)}. So this colouring uses at most k − 1 colours.
m
Consider two distinct edges (ai , bp ), (ai , bq ) incident on a vertex ai . Since p ≠ q and
.co
1 ⩽ p, q ⩽ k we get that (i − p) mod k ≠ (i − q) mod k holds. Thus no two edges
m
s e
l a
incident with a vertex ai get the same colour under this colouring. By a symmetric
ag
argument this holds for edges incident with vertices bj , as well. So the algorithm gives
an edge colouring of the graph using the optimal number of colours.
(b) The number of colours used by the algorithm is k − 1. ⊣

4. In the Pots-of-Gold game, there is a row of n pots P1 , … , Pn . Each pot contains some number
of gold coins. You remove pots and collect the gold coins from the pots that you remove,
subject to the rules below. Your aim is to collect as many gold coins as possible.

• You start with no gold coins and remove pots one at a time. You can remove any pot m
m that is available for removal. .co
m .co s em
• In the beginning, all pots are available for removal. Removing pot Pi makes the pots

s e Pi−1 and Pi+1 (if they exist) permanently unavailable.
g la
g la a
(a) Assuming that we have an array G[1 … n] with G[i] storing the number of gold coins in
a pot Pi , devise an algorithm PotsOfGold(G, n) that computes the maximum number
of gold coins that you can collect. Your algorithm should run in O(n) time in the worst
case. You can assume that each arithmetic operation involving two integers, and each
array access (reading/writing one element) takes constant time. Hint: Use dynamic
programming.
(b) Clearly explain why your procedure of part (a) correctly computes the required output.
(c) Explain why your procedure of part (a) runs in O(n) time in the worst case.
m .
.co s e m
s em 9
l a
g la ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 9 of 12

function PotsOfGold(G, n)
if n = 1 then
(a)

return G[1]

Let dp[1 … n] be a new array
end if

dp[1] ← G[1]
dp[2] ← max(G[1], G[2])
for all i ∈ {3, … , n} do
dp[i] ← max(dp[i − 1], dp[i − 2] + G[i])

return dp[n]
end for

end function
(b) Let dp[i] denote the maximum number of gold coins the player can collect from pots
P1 , P2 , … , P i .
For i ⩾ 3,
dp[i] = max(dp[i − 1], dp[i − 2] + G[i]).

This holds because the player either does not take pot Pi (optimal value is dp[i − 1])
or takes pot Pi (in which case they cannot take pot Pi−1 , so the optimal value is dp[i −
2] + G[i]). The base cases dp[1] = G[1] and dp[2] = max(G[1], G[2]) are immediate. By
mathematical induction on i, the value returned by the procedure is correct.
(c) The algorithm performs a constant amount of work for the special case n = 1 and for
initializing dp[1] and dp[2]. The for loop then executes exactly n − 2 times (when n ⩾ 2),
with O(1) work in each iteration. Hence the running time is O(n). ⊣

5. In this question, we only consider real-valued functions from [0, 1] → ℝ.

point in (0, 1]?
(a) Does there exist a function f that is continuous at exactly 0 and discontinuous at every

(b) Suppose S is a finite subset of [0, 1]. Does there exist a function that is continuous at
all points in S, and discontinuous everywhere else?

Justify your answers with proofs.

Answer. Let S = {x1 , … , xk } (Set S = {0} for part (a)). Define

∏i=1 (x − xi )
f (x ) = {
k
if x is rational
0 otherwise

f is continuous at each xi ∈ S. Let p(x ) = ∏ki=1 (x − xi ). This is a continuous function.
Hence, for each ε > 0, there exists δ > 0 such that for all x with |x − xi | < δ, |p(x ) − p(xi )| < ε.
But, for all x such that |x − xi | < δ, |f (x ) − f (xi )| = |p(x ) − p(xi )| < ε if x is rational; since
f (xi ) = 0, this quantity is 0 when x is irrational. This proves continuity.

10

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 10 of 12

m
m .co

m .co s em
se g la
f is discontinuous at each x ∉ S. Suppose x is rational.
a For any δ > 0, there exists an
irrational y such that |x − y| < δ since irrational numbers are dense in ℝ. Furthermore,
when y is irrational, |f (y) − f (x )| = |f (x )| = |p(x )| > 0, where the last inequality follows from
the definition of p. Thus, for all 0 < ε < |p(x )|, there exists no δ such that |f (x ) − f (y)| < ε for
all y such that |x − y| < δ.
Suppose x is irrational. For any 0 < ε < |p(x )|/2, appealing to continuity of p, choose δ such
that |p(x ) − p(y)| < |p(x )|/2 for all y such that |x − y| < δ. Then, for all rational y such that
|x − y| < δ, |f (x )− f (y)| = |f (y)| = |p(y)| > |p(x )|/2 by the choice of δ. But this is more than the m
given ε. Thus there exists ε for which, no matter what δ > 0 we pick, we can find a rational
m .co
y such that |x − y| < δ (since rationals are dense in ℝ) but |f (x ) − f (y)| > ε.
.co e m
We have thus proved that f is discontinuous at each x ∉ S, whether x ∈ ℚ or not.
em ⊣la
s
l a s ag
6. Let xa, … , x be uniform, independent bits; i.e., each x is a random variable that takes value
1
g n i

(x1 , .., xn ) are said to be independent if, for all b1 ∈ {0, 1}, b2 ∈ {0, 1}, … , bn ∈ {0, 1},
0 or 1 with equal probability, and is independent of the other random variables. Recall:

P [x1 = b1 , x2 = b2 , … , xn = bn ] = P [x1 = b1 ] × P [x2 = b2 ] × … × P [xn = bn ] .

A set of bits y1 , … , yn is said to be pairwise independent if, for every distinct i, j ∈ {1, 2, … , n},
the bits yi and yj are independent.

(a) Prove that x1 , x2 , and x1 ⊕ x2 are pairwise independent when ⊕ denotes binary addition
m
(exclusive OR); i.e., x1 ⊕ x2 = x1 + x2 mod 2. .co
em
(b) Prove that x1 ⊕ x2 , x1 ⊕ x3 , and x3 ⊕ x2 are pairwise independent.
s
l a
a g
(c) Can you create 7 pairwise independent bits using x , x , x ? Justify your answer.
(d) Generalize this to show that n uniform, independent bits can be used to generate 2n − 1
1 2 3

pairwise independent sets. Justify your answer.

(a) This is a basic exercise in probability.
(b) This too is a basic exercise in probability.
m
m (c) The answer is ‘Yes’. Consider all nonzero linear combinations:
.co
m .co em
x1 , x2 , x3 , x1 ⊕ x2 , x1 ⊕ x3 , x2 ⊕ x3 , x1 ⊕ x2 ⊕ x3 .
s
s e la can be shown to
These are 2 − 1 = 7 distinct bits. Any two distinct such combinations
g
g la 3
a
a be pairwise independent as in part (a) and (b).
(d) We claim that for any distinct nonempty subsets S, S′ ⊆ [n], ⊕i∈S xi and ⊕i∈S′ xi are
independent. This is easily seen by noting that at least two of S ∩ S′ , S ∖ S′ , and S′ ∖ S
are non-empty, and

⊕i∈S∩S′ xi , ⊕i∈S∖S′ xi , ⊕i∈S′∖S xi

are independent. Now, setting these parities to y1 , y2 , y3 , we can show the required
independence using (a) and (b). This gives us 2n − 1 pairwise independent sets.
m ⊣ .
.co s e m
s em 11
l a
g la ag
a For more Question Papers, Sample Papers, Notes & Syllabus visit Page 11 of 12

7. Let Mn (ℝ) denote the vector space V of all n × n matrices over the real numbers ℝ. You may
assume that eij are the basis vectors of this vector space and xij are the dual basis. Recall that
a matrix is said to be singular if its determinant is zero.

(a) Let Eij be the matrix with 1 in position (i, j) and zeros elsewhere. Describe a linear sub-
space L ⊆ V of dimension n2 − n containing the elementary matrix Eij such that all
matrices in L are singular. If it helps, you may write down a system of linear equa-
tions in the variables xij whose solution space contains Eij and has the requisite dimen-
sion.
(b) Let A ∈ Mn (ℝ) be a matrix of rank less than or equal to n − 1. Show that there exists a
linear subspace L ⊆ V such that A ∈ L , every matrix in L is singular and dim L ⩾
n2 − n.

(a) Let k ≠ i. Then a linear subspace containing Eij is xks = 0, 1 ⩽ s ⩽ n. This subspace has
dimension n2 − n. Clearly all matrices satisfying these equations have their k-th row
zero and are singular.
(b) W.l.o.g we may assume that the last row is a linear combination of the first n − 1 rows.
Then there are real numbers λ1 , λ2 , … , λn−1 such that for 1 ⩽ j ⩽ n, anj = ∑ii==1n−1 λi aij .
Let us define L to be the set of matrices satisfying xnj = ∑ii==1n−1 λi xij for all j. Clearly
A ∈ L . Furthermore, L is the solution space to a system of n equations in n2 vari-

linearly on the first n − 1 rows, and so M is singular. The solution space has dimension
ables. Since every matrix M in L satisfies these equations, the n-th row of M depends

at least n2 − n. ⊣

8. Consider a bivariate function f ∶ ℝ × ℝ → ℝ.

(a) What does it mean to say f is continuous at a point (a, b) ∈ ℝ × ℝ? Can you define it
formally?
(b) Consider any straight line L passing through the point (a, b). Show that f restricted to
the line is a real function fL ∶ ℝ → ℝ.
(c) If fL is continuous at the point (a, b) for each line L passing through (a, b) then is the
bivariate function f continuous at (a, b)?

Justify answers with proofs.

(a) For every ε > 0 there is a δ > 0 such that if (x , y) is in the δ-disc centered at (a, b) then
|f (x , y) − f (a, b)| < ε.
(b) Points on a line L through (a, b) is of the form (a + tα, b + tβ) for real α and β (at least one
is non-zero). Then fL (t ) = f (a + tα, b + tβ) defines the desired one-variable real-valued
function.
(c) Not necessarily. The function f (x , y) = 4 is discontinuous at (0, 0) but along
x + y2
x2y

every line L through (0, 0) the function fL is continuous at (0, 0). ⊣

12

For more Question Papers, Sample Papers, Notes & Syllabus visit Page 12 of 12