CMI Entrance Exam 2023 Question Paper Solution M.Sc PhD Computer Science

CHENNAI MATHEMATICAL INSTITUTE
M.Sc. / Ph.D. Programme in Computer Science
Entrance Examination, 2023

This question paper has 5 printed sides. Part A has 10 questions of 3 marks each. Each
question in Part A has four choices, of which exactly one is correct. Part B has 7 questions
of 10 marks each.
The total marks are 100. Answers to Part A must be filled in the answer sheet provided.
In all questions related to graphs, unless otherwise specified, we use the word “graph”
to mean an undirected graph with no self-loops, and at most one edge between any pair of
vertices.

Part A
1. A candy factory uses 5 fruit flavours {A, B, C, D, E}. Each candy is made using one or
more of these flavours. The taste of a candy depends on which flavours are included.
A kid may prefer some combination of flavours more than others. For example, the
kid may prefer the combination {A, B, C} over {B, C}. The preference order of a kid
is a total ordering of all the combinations, the ones occurring earlier being preferred
more.
Suppose you want to throw a party and do not want more than one kid with the same
preference order. What is the maximum number of kids that can attend such a party?
(a) (2(5!) ) − 1 (b) ((25 ) − 1)! (c) ((5 ∗ 4)/2) − 1 (d) 5 ∗ 5

Answer: (b) ((25 ) − 1)!

Each nonempty subset of the set of 5 fruit flavours will result in a distinct taste. So
there are F = (25 ) − 1 tastes. These can be arranged in F ! ways, which is the number
of distinct preference orders. Inviting more than these many kids will result in at least
two kids having the same preference order, by the pigeon hole principle. Hence (b) is
the answer.
⊣

2. How many elements are in the following set?

{(A, B) | A ⊆ B ⊆ {1, 2, 3, . . . , n}}

(a) 2n−1 (b) 3n (c) 2n+1 (d) 22n

Answer: (b) 3n

For each pair (A, B), we can define a function fA,B : {1, . . . , n} → {a, b, c}as follows:


a if i ∈ A \ B
fA,B (i) = b if i ∈ B \ A


c if i ∈ A ∩ B (i is common to A and B)

1

For each function f : {1, . . . , n} → {a, b, c}, we can define a pair (Af , Bf ) as follows:

Af = {i | f (i) = a or f (i) = c} Bf = {i | f (i) = b or f (i) = c}

The total number of functions from {1, . . . , n} to {a, b, c} is 3n . ⊣

3. At a kindergarten, 2024 kids sit in a circle. Suddenly, each kid randomly pokes either
the kid to their left or the one to their right. What is the expected number of unpoked
kids?
(a) 1 (b) 253 (c) 506 (d) 1012

Answer: (c) 506

Each kid chooses left or right with probability 12 and pokes that neighbour. A kid is
unpoked if its right neighbour chooses right and its left neighbour chooses left. The
probability that this happens is 14 . There are 2024 kids in all. Therefore, the expected
number of unpoked kids is 41 × 2024 = 506. ⊣

4. A graph is k-regular if all the vertices have degree exactly k. What is the minimum
number of vertices in a k-regular graph that has no 3-length cycles?
(a) k (b) k + 1 (c) 2k (d) 2k + 1

Answer: (c) 2k

Consider any k-regular graph with < 2k vertices, and two vertices u and v with an
edge between them. Other than v, u has k − 1 neighbours. Other than u, v has
k − 1 neighbours. But the number of vertices other than u and v is strictly less than
2k − 2 = 2(k − 1). Thus there is a vertex w which is a common neighbour to both u
and v, and u − v − w is a cycle of length 3.
The complete bipartite graph on 2k vertices, Kk,k , is k-regular and has no odd cycles.
So 2k is the minimum number of vertices needed for a k-regular graph to not have
cycles of length 3. ⊣

5. In a connected graph, any two paths of maximum length:

(a) have at least one vertex in common, but not necessarily an edge in common
(b) have at least one edge in common
(c) have at least two common vertices, but not necessarily an edge in common
(d) have at least two edges in common

2

Answer: (a)

Consider two paths of maximum length, p = u1 . . . un and q = v1 . . . vn , with no
common vertex between them. Since the graph is connected, there is a path from
every ui to every vj . Choose i and j such that there is a path from ui to vj without
passing through any vertex in either p or q. Choose l and k as follows:
{ {
n if i ≤ n2 n if j ≤ n2
l= k=
1 otherwise 1 otherwise

One can verify that the path ul . . . ui . . . vj . . . vk has length > n, which is a contra-
diction. Thus two paths of maximum length in a connected graph have a common
vertex.
Consider the graph G = (V, E) with V = {v0 , . . . , v4 } and E = {(v0 , vi ) | 1 ≤ i ≤ 4}.
The maximum length of any path is 2, and all such paths have a single common vertex
v0 , but no common edge. Thus (a) is the correct option. ⊣

6. Consider the automaton over the alphabet {a, b, c} shown in Figure 1. The initial
state is the leftmost state. States with a double circle are accepting states.

a, b
a, b
b, c
b, c

c, a
c, a

Figure 1: Automaton for Question 6

What is the complement of the language accepted by this automaton?
(a) {ε} (b) c∗ + a∗ + b∗ (c) (a + b)∗ + (b + c)∗ + (c + a)∗ (d) None of the above

Answer: (d) None of the above

By the alphabet of a string, we mean the set of all letters occurring in the string. The
language accepted by the automaton is all strings whose alphabet is of size 1 or 2.
The complement is the language consisting of all strings whose alphabet is of size 0
or 3. The regular expressions in options (a), (b) and (c) do not capture this language.
So the correct answer is (d). ⊣

7. Let L be a regular language, and let n = 10. Which of the following statements is
true?

(a) L ∪ {an bn } is regular
(b) L ∪ {an bn } is context-free, but not regular
(c) L ∪ {an bn } is regular, but not context-free
(d) L ∪ {an bn } is not context-free

3

Answer: (a)

{an bn } is a set with one element, and hence regular. L ∪ {an bn } is a union of two
regular languages, and hence regular. ⊣

8. Let f : N → N and g : N → N be functions over the set N of natural numbers. We
will say:

• f (n) = O(g(n)) if there exist natural numbers c and x0 such that f (n) ≤ c g(n)
for all n ≥ x0
• f (n) = 2O(g(n)) if there exist natural numbers c and x0 such that f (n) ≤ 2(c g(n))
for all n ≥ x0 .

Consider the following statements

(I) 3n = O(2n ) (II) 3n = 2O(n)

(a) Both (I) and (II) are true (b) (I) is true and (II) is false
(c) (I) is false and (II) is true (d) Both (I) and (II) are false

Answer: (c) Statement (I) is false and Statement (II) is true

Since 32 > 1, for any fixed c we can find n large enough such that ( 23 )n > c, i.e.,
3n > c · 2n . Therefore it is never the case that there exist c and x0 such that 3n ≤ c · 2n
for all n ≥ x0 . In other words, statement (I) is false.
Statement (II) is true. We take c = 2 and x0 = 1. Then 3n ≤ 4n = 2c·n . ⊣

The next two questions refer to the following two functions. We assume that all the
arguments are non-negative integers. The operation x div 2 divides x by 2 and returns
an integer, discarding the fractional part.

int f(int x, int i) { int g(int x) {
if (i == 0) { if (x <= 2)
if (even x) return 1;
return 0; else
else return 1 + g(x div 3);
return 1; }
} else {
return f(x div 2, i-1);
}
}
9. For how many values of i will f(1000,i) return 1?
(a) 2 (b) 5 (c) 6 (d) 10

4

Answer: (c) 6

It can be seen that f (x, i) returns the ith bit in the binary expansion of x, counting the
least significant bit as the 0th bit. Now the binary expansion of 1000 is 1111101000,
so f (x, i) returns 1 for six different values of i. ⊣

10. What is the value of g(10000)?
(a) 3 (b) 9 (c) 12 (d) 15

Answer: (b) 9

It can be seen that g(x) returns the number of digits in the ternary (base 3) represen-
tation of x. Now 10000 in base 3 is 111201101, whose length is 9. ⊣

5

Part B
1. Let Σ = {a, b} be an alphabet. A palindrome is a word which reads the same when
read from left-to-right, or from right-to-left. For example, the words abba, aba and aa
are palindromes, whereas aabb and ab are not. A palindrome is said to be non-trivial
if it has length at least 2.
Let L be the set of all words that contain a non-trivial palindrome as a prefix, that is,

L = {w ∈ Σ∗ | w = uv for some non-trivial palindrome u and some v ∈ Σ∗ }

(a) Give an example of a word in L, which is not a palindrome.
(b) Give three examples of words not in L.
/ L for some x ∈ Σ∗ . What can you say about x?
(c) Suppose ax ∈
(d) Show that L is regular.

Answer:

(a) aab ∈ L since it has the palindrome aa as prefix, but it itself is not a palindrome.
(b) One can check that ab, abb and abbb are not in L.
(c) If the first letter of x is a, then ax has aa, a non-trivial palindrome, as a prefix.
Hence ax ∈ L. Thus, whenever ax ∈ / L, x is either the empty string or of the
form by.
(d) From the above, we can see that the complement of L is regular, since it is
generated by the following regular expression.

ε + a(ε + bΣ∗ ) + b(ε + aΣ∗ ).

Hence L is also regular, since the complement of a regular language is regular.

⊣

2. A non-empty collection S of subsets of a set U is a scattering of U if it satisfies the
following condition:

for all A, B ∈ S, A is not a proper subset of B.

(a) Let U = {1, 2, 3, 4, 5}. Give an example of a scattering of U .
(b) Is the following statement true? Justify your answer with a proof or a counterex-
ample.
• F is a scattering of U if and only if {U \ A | A ∈ F} is a scattering of U ,
where U \ A denotes the complement of A with respect to U .

6

Answer:

(a) An example is the collection {{1}, {2}, {3}, {4}, {5}}. Another example is the
collection {{1, 2, 3, 4}, {2, 5}}.
(b) For any A, B ⊆ U , A is a proper subset of B iff U \ B is a proper subset of U \ A.
Thus F is a scattering iff {U \ A | A ∈ F } is a scattering.

⊣

3. Let a1 , . . . , an be integers. Show that for some k, m such that 1 ≤ k ≤ m ≤ n, the
sum ak + ak+1 + · · · + am is divisible by n. (Hint: Consider the sums a1 + · · · + ai
modulo n, for 1 ≤ i ≤ n.)

Answer: For 1 ≤ i ≤ n, let Si = a1 + · · · + ai , and let ri = Si mod n. If ri = 0 for
some i, it means that a1 + · · · + ai is divisible by n, so we choose k = 1 and m = i.
If not, then each ri is in the set {1, . . . , n − 1}. By the pigeonhole principle, we have
ri = rj for some 1 ≤ i < j ≤ n. But then rj − ri = ai+1 + · · · + aj is divisible by n. So
we choose k = i + 1 and m = j. ⊣

4. On the island of Knights, Knaves, and Normals, Knights always tell the truth, Knaves
always lie, and Normals sometimes tell the truth and lie sometimes.
One day Professor Raymond visited this island and met two inhabitants, A and B.
He already knew that one of them was a Knight and the other was a Normal, but
he didn’t know which was which. He asked A whether B was normal, and received
a Yes-or-No answer. Professor Raymond was then able to figure out who the Knight
was.
Who was the Knight – A or B?

Answer: Suppose the answer he received was “Yes”. Then it is possible that A was
a Knight and was telling the truth about B, or that A was a Normal who was lying
about B. So Raymond would not be able to figure out who was the Knight. Since he
figured out, he must have received a “No” answer. Now if A was a Knight, he wouldn’t
have lied about B (B is Normal, so answering “No” constitutes a lie). So it has to be
the case that A was a Normal, and B was a Knight. (Additionally, it so happens that
in this case A was telling the truth.) ⊣

5. You are starting a new bus service. You are hiring drivers and conductors. A driver
and a conductor can run a bus only if they can speak a common language. There
are n drivers and m conductors who have applied for a job. Their CV has a list of
languages they speak.

(a) Given the CVs of the drivers and conductors, we want to calculate the maximum
number of buses that can be run. Show how to use graph matching to solve this
problem. (Note: You do not need to solve graph matching itself. Just demonstrate
how to use it for this problem.)
(b) You are in a hurry to get the bus service running. Whenever you get a new
application from a driver (or a conductor), you check if you can team this new
candidate with an existing conductor (or driver) who is free. If yes, you assign the

7

pair of them to a bus. If no, then the new candidate is added to the list of free
driver (or conductors).
Provide an example scenario where the above procedure does not compute the
maximum number of buses that can be run.

Answer:

(a) Form a bipartite graph with drivers and conductors as vertices, and an edge
between a driver and a conductor whenever they speak a common language.
Since the same driver (or the same conductor) cannot run two buses at the same
time, an assignment of drivers and conductors to buses corresponds to a matching
in the graph. We can find the maximum number of buses that can be run by
computing a maximum matching in this bipartite graph.
(b) Suppose three drivers and three conductors apply, in the order D1 C1 D2 C2 D3 C3 .
Also suppose that D1 knows Bengali, Tamil and Malayalam, C1 and D2 know
only Tamil, C2 and D3 know only Malayalam, and C3 knows only Bengali. The
above algorithm will match D1 with C1 , put D2 on the bench, pair C2 and D3 ,
and also put C3 on the bench, thus running two buses in parallel.
But this is not the optimal pairing. By pairing D1 with C3 , D2 with C1 and D3
with C2 , we can run three buses in parallel.

⊣

6. The input to the problem consists of (i) an array A[1, 2, . . . , n] of n positive integers
and (ii) a positive integer T . We are given the guarantee that at least one element
of the array is less than or equal to T . The task is to find the maximum sum of a
non-empty sub-collection of the integers from A which is less than or equal to T .
Describe an algorithm that solves this problem in O(nT ) time. The algorithm should
take an array A[1, 2, . . . , n] and an integer T as described above, and should output
a number T ′ ≤ T that is closest to T and can be realized as the sum of some sub-
collection of A. It is not required that the algorithm find the subset of indices which
forms the sum T ′ .

Answer: For 0 ≤ i ≤ n and t ≤ T , let p(i, t) be defined as follows:
 ∑
1 if there is S ⊆ {A[1], . . . , A[i]} s.t. x=t
p(i, t) = x∈S

0 otherwise

We see that p(0, 0) = 1 and p(0, t) = 0 for all 1 ≤ t ≤ T . For i > 0, we see that the
following recurrence holds:

p(i, t) = 1 iff p(i − 1, t) = 1 or p(i − 1, t − A[i]) = 1.

Now we just need to return the maximum t for which p(i, t) = 1.
We can use the above recurrence to compute all p(i, t) values and the final T ′ , as
described in the pseudocode below. It is easily checked that the code runs in O(nT )
time.

8

int array P[0..n][0..T];
P[0][0] = 1;
for t = 1 to T {
P[0][t] = 0;
}
for i = 1 to n {
for t = 0 to T {
if (P[i-1][t] == 1 || (t >= A[i] &&
P[i-1][t-A[i]] == 1)) {
P[i][t] = 1;
} else {
P[i][t] = 0;
}
}
}
t = T;
while t >= 0 {
if P[n][t] == 1 {
break;
} else {
t = t - 1;
}
}
return t;

⊣

7. Consider the following code which computes a function f. The input to f is an
array A[1..m] which represents a number N in ternary. For example, A = [1, 2, 0]
represents the number 15 since 15 = 1 × 32 + 2 × 31 + 0 × 30 ; and A = [1,0,0,0]
represents the number 27. Function f uses the function pow(x,y) that returns xy .
You may assume that the first element in the array is not zero.

int f(A[1..m]) {
x = 1;
for j = 1 to m {
x = pow(x, 3);
y = pow(3, A[j]);
x = x * y;
}
return x;
}

(a) What are f([1,2]), f([1,2,0]) and f([1,2,2])?
(b) Suppose array A represents the number N. What is f(A) in terms of N?

9

Answer:

1. One can check that the values are 35 = 243, 315 = 14348907 and 317 = 129140163.

2. For 0 ≤ j ≤ m, let v(j) be the number represented by A[1..j]. We claim that if
v(m) = N , then f (A) = 3N .
We show by induction on 0 ≤ j ≤ m that at the end of j iterations of the loop, the
value of x is 3v(j) .

• When j = 0, we adopt the convention that we are at the start of the loop,
after x has been assigned the value 1. We also adopt the convention that
v(0), the value of the empty array segment A[1..0], is 0. Clearly in this case,
x = 1 = 30 = 3v(0) .
• Suppose the claim is true for j < m. Note that v(j + 1) = 3 · v(j) + A[j + 1].
At the end of j iterations, x has value 3v(j) , and in the (j + 1)-st iteration, the
sequence of state changes that happens is as follows:

x ← (3v(j) )3 = 33·v(j) , y ← 3A[j+1] , x ← 33·v(j) · 3A[j+1] = 33·v(j)+A[j+1] = 3v(j+1) .

At the end of the loop (i.e., after m iterations), we return 3v(m) = 3N , as desired.

⊣

10