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

FOR CMI EXAM PREPARATION

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

CMI 2026 Question Paper 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
a INSTITUTE
CHENNAI MATHEMATICAL
M.Sc. / Ph.D. Programme in Computer Science
Entrance Examination, May 2, 2026

• This examination has three parts: Part A, Part B and Part C.

– Time allowed: 3 hours
m
.co
– Total marks: 100
m
.co
• Part A consists of 10 multiple choice questions, each carrying 3 marks. There
s e m
em a
may be multiple correct choices. You have to select all the correct options and no
s l
la ag
incorrect option to get full marks. There is no partial credit, and no negative
g
marking.
a
• Part B has 3 long-answer questions, each carrying 10 marks.

• Part C has 8 long-answer questions, each carrying 10 marks. Students can choose
any 4 out of these 8 questions. Students may attempt more than 4 questions; in
such cases, the best 4 answers will be considered for the final score.

• For questions in Part A, you have to provide the answers on the computer. You only
have to choose the appropriate answer(s) from the choices provided. For example,
m
.co
if the correct choices for a question are options (a) and (c), choose only (a) and (c)

m
to score full marks for that question.

s e
a
In all questions related to graphs, unless otherwise specified, we use the word
l
ag
“graph” to mean a finite undirected graph with no self-loops, and at most one
edge between any pair of vertices.

Part A
1. Six people A, B, C, D, E, F sit around a circular table.

• A sits opposite D
• B is not adjacent to A
m
.co
• C sits immediately to the right of B
m • E is adjacent to D
m .co s e m
s e Who sits opposite C?
g la
g la (a) B (b) D (c) E a (d) F
a 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 is not played (b) Abhay did not dance
(c) Bharat did not juggle (d) Dhruva left the party
m .
.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 8

3. Suppose you are writing a 100-question multiple-choice exam with 4 choices per ques-
tion and exactly one correct answer. You know the answers to 80% of the questions,
and you 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

4. In a multiple choice test with 100 questions, each question has 5 possible answers
with exactly 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
correctly, 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
5. 1000 candidates appear in a competitive examination. There are 50 questions, each
worth 2 marks. There is no partial credit, and each answer is awarded either 0 marks
or 2 marks. Only 10 candidates scored 80 or above. Let ni (0 ≤ i ≤ 100) denote the
number of candidates 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.
(d) There are at most 30 values of i ∈ {0, . . . , 100} such that ni = 0.

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.

3

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)?

(a) T (2) = 3
(b) T (n) = 0 for all odd n.
(c) T (n) is given by a recurrence of the form T (n) = T (n − 1) + T (n − 2).
(d) 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

2

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

m
m .co

m .co s em
se g la
a the function f (x), where
Questions 8 and 9 pertain to the following pseudocode defining
x is assumed to be a nonnegative integer. The code uses the function rem(n, d), which
returns the remainder after dividing n by d.
function f (x)
a←0
while x > 0 do
r ← rem(x, 2)
a ← (10 × a) + r
m
x ← (x − r)/2
m .co
.co e m
end while
return a
em l as
as
end function
l ag
g
a is the value returned by f (43)?
8. What
(a) 101000 (b) 101011 (c) 110101 (d) 110100

9. Which of the following best describes the running time of f (x)?
(a) Linear in x. (b) Quadratic in x.
(c) Logarithmic in x. (d) Exponential in x.
10. Consider the following two procedures proc1 and proc2, which run in parallel after
m
initializing x to 6 and y to 3. Running in parallel means that between any two lines

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

l as
ag
int x = 6, y = 3;

proc1 { proc2 {
x = 2*y; y = 2*x;
x = x - y; y = y - x;
} }

Which of the following values are possible for (x,y) after both processes have come
m
c. (d)o (36,-12)
to a halt?
m
c. o (a) (8,5) (b) (3,3) (c) (0,6)
s e m
e m la
las ag
ag

m .
.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 8

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.

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

4

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

m
m .co

m .co s em
se g la
2. For a set X, X denotes the set of all strings formeda using X, including the empty
∗

string. By xy, we mean the concatenation of x and y, i.e., the string x followed by
the string y. We say 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 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
m
c o m
f : Σ∗ → {0, 1}∗ is a prefix-free homomorphism.
m .co
. that f (a) is of length at most 3 for all a. If so, define such an f . If se
em a proof that this is not possible. a
(a) Is it possible

as
not, provide
g l
(b) Isglit possible that f (a) is of length 2 for some a ∈ Σ and f (b) is of length 3afor
aall b ∈ Σ \ {a}. If so, define such an f . If not, provide a proof that this is not
possible.
(c) Show that there are no distinct x, y ∈ Σ∗ such that f (x) = f (y).

3. Suppose G = (V, E) is a graph with |V | = 2k for some k ≥ 1. Further, suppose there
is no cycle of length 3 in G, i.e., G is triangle-free. Prove that |E| ≤ k 2 .

m
m .co
s e
l a
ag

m
m .co
m .co s e m
s e g la
g la a
a

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 8

Part C
1. Consider a finite alphabet Σ = {0, 1}. For a string w ∈ Σ∗ , we write |w| for the length
of w. For two strings 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.

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.

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 sharing a common vertex receive the same color.

(a) Give an efficient algorithm to color the edges of the graph with minimum number
of colors.
(b) How many colors does your algorithm use?

6

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

m
m .co

m .co s em
se g la
4. In the Pots-of-Gold game, there is a row of n pots P , a
. . . , P . Each pot contains some
1 n
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 that is available for removal.
• In the beginning, all pots are available for removal. Removing pot Pi makes the
m
m .co
pots Pi−1 and Pi+1 (if they exist) permanently unavailable.

m .co
(a) Assuming that we have an array G[1 . . . n] with G[i] storing the number of gold
s e m
s e l a
ag
coins in pot Pi , devise an algorithm PotsOfGold(G, n) that computes the
l a
maximum number of gold coins that you can collect. Your algorithm should run
g
ain 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.

5. In this question, we only consider real-valued functions from [0, 1] → R.
m
.co
(a) Does there exist a function f that is continuous at exactly 0 and discontinuous
m
at every point in (0, 1]?
s e
(b) Suppose S is a finite subset of [0,a1]. Does there exist a function that is continuous
l
ag everywhere else?
at all points in S, and discontinuous

Justify your answers with proofs.

6. Let x1 , . . . , xn be uniform, independent bits; i.e., each xi is a random variable that
takes value 0 or 1 with equal probability, and is independent of the other random
variables. Recall: (x1 , .., xn ) are said to be independent if, for all b1 ∈ {0, 1}, b2 ∈
{0, 1}, . . . , bn ∈ {0, 1},

o m
P [x1 = b1 , x2 = b2 , . . . , xn = bn ] = P [x1 = b1 ] × P [x2 = b2 ] × . . . × P [xn = bn ] .
m c
.distinct i, j ∈
c. o A{1,set2, .of. . ,bits1
e m
y , . . . , y is said to be pairwise independent if, for every
n
s
e m n}, the bits y and y are independent.
l a
s
i j

la g
a when ⊕ denotes binary
g
(a) Prove that x , x , and x ⊕ x are pairwise independent
a
1 2 1 2
addition (exclusive OR); i.e., x ⊕ x1= x2 + x mod
1 2. 2

(b) Prove that x1 ⊕ x2 , x1 ⊕ x3 , and x3 ⊕ x2 are pairwise independent.
(c) Can you create 7 pairwise independent bits using x1 , x2 , x3 ? Justify your answer.
(d) Generalize this to show that n uniform, independent bits can be used to generate
2n − 1 pairwise independent sets. Justify your answer.

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 8

7. Let Mn (R) denote the vector space V of all n × n matrices over the real numbers R.
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 subspace 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 equations in the variables xij whose solution space contains Eij
and has the requisite dimension.
(b) Let A ∈ Mn (R) 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.

8. Consider a bivariate function f : R × R → R.

(a) What does it mean to say f is continuous at a point (a, b) ∈ R × R? Can you
define it formally?
(b) Consider any straight line L passing through the point (a, b). Show that f re-
stricted to the line is a real function fL : R → R.
(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.

8

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