CMI Entrance Exam 2022 Question Paper Solution M.Sc Computer

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

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.

Part A
1. If Vinay finishes his homework and the school closes early, then he can play in the
park or eat an ice cream. He will end up at the dispensary with tummy ache if he eats
ice cream and plays in the park. Which of the following can be correctly inferred?

(a) If he doesn’t end up in the dispensary with tummy ache, then he did not finish
his homework or the school closed late.
(b) If he doesn’t end up in the dispensary with tummy ache, he didn’t eat ice cream
and he didn’t play in the park.
(c) Both (a) and (b)
(d) None of the above.

Answer: (d) None of the above

(a) is not possible, because Vinay can finish his homework, the school can close early,
and he plays in the park without eating icecream. In this case he will not end up in
the dispensary, but neither of the conclusions in (a) can be inferred.
(b) is not possible, again because Vinay can play in the park without eating icecream,
or eat icecream without playing in the park. In both cases, he does not end up in the
dispensary. So one cannot infer the conjunction of the two conclusions in (b).
Hence the correct answer is (d). ⊣

2. There are n members of Chennai Mathematical Institute. Most of them are very
studious, and like to own lots of books. Now the following facts have been learnt.

• No two members own exactly the same number of books.
• Each member owns strictly less than n books.
• No member has exactly 200 books.

Given the above information, which of the following is not a possible value of n?

(a) 100
(b) 199
(c) 200
(d) 201

1

Answer: (d) 201

Number the CMI members as 1, 2, . . . , n, and let bi be the number of books owned
by i. It is given that 0 ≤ bi < n for each i ≤ n, so the set of bi ’s is a subset of
{0, . . . , n − 1}. It is also given that bi ̸= bj for distinct indices i and j, so the set of
bi ’s has to be of size n. From this it follows that the set is exactly {0, . . . , n − 1}. If
n = 201, then n − 1 = 200, and that contradicts the fact that no one has 200 books.
Thus (d) is not possible. One can verify that the other three choices are possible. ⊣

3. Which of the following assertions about regular languages is incorrect?

(a) Every subset of a regular language is regular.
(b) For every regular language L, there is a subset of L that is regular.
(c) For every language L, there is a superset of L that is regular.
(d) The complement of every regular language is regular.

Answer: (a) Every subset of a regular language is regular.

To see that (a) is incorrect, observe that {a, b}∗ is regular, while the subset {an bn |
n ≥ 0} is not regular.
Option (b) is correct since ∅, which is regular, is a subset of every language. (c) is
also correct, since Σ∗ is regular, and is a superset of any regular language L over the
alphabet Σ. Complements of regular languages are also regular, as one can build a
DFA for any language and swap the final and non-final states to get an automaton for
the complement. ⊣

4. Consider the following languages over the alphabet {a, b, c, d}

• L1 = {an bn cm dm | n, m ≥ 0}
• L2 = {an bm cn dm | n, m ≥ 0}
• L3 = {an bm cm dn | n, m ≥ 0}

Which of these languages is/are context-free?

(a) None of them.
(b) Only L1 and L2 .
(c) Only L1 and L3 .
(d) All of them.

Answer: (c) Only L1 and L3 are context-free.

L1 is generated by the grammar S → T U ; T → aT b | ε; U → cU d | ε.
L3 is generated by the grammar S → aSd | T ; T → bT c | ε.
One can apply the pumping lemma for CFLs to show that L2 is not context-free. ⊣

2

5. As part of a class activity, students in a class of 50 were asked to keep track of the
total number of hours that they spent looking at the screen of some digital device on a
specific day. It was found that the average screentime for the class was 4 hours. What
is the maximum possible number of students with at least 16 hours of screentime?
(a) 11
(b) 12
(c) 13
(d) 14

Answer: (b) 12

The total screentime (for all 50 students) is 200. 13 students spending 16 hours
amounts to 208, which is more than the total. 12 students spending 16 hours amounts
to 192, which is within the total time. Thus the maximum number of students with
at least 16 hours of screentime is 12. ⊣

6. The Telvio mobile service provider allows each customer to choose a part of their 10-
digit mobile number when getting a new connection. The first two digits of the number
are fixed by the company based on the customer’s region. The customer can choose
the last four digits as they wish. The company chooses each of the remaining four
digits uniformly at random, and without replacement, from the list {0, 1, 2, . . . , 9}.
Note that this means that the digits in positions 3, 4, 5 and 6 in a Telvio number are
all different.
What is the probability that in the mobile number assigned to a new customer by
Telvio, the digits in positions 3, 4, 5 and 6 appear in increasing order when read from
left to right?
(a) 14
1
(b) 16
1
(c) 24
1
(d) 32

1
Answer: (c) 24

For each choice of four distinct digits, there is exactly one way to write them in
increasing order. The number of possible ways of ordering four distinct digits is 24.
1
Thus the answer is 24 . ⊣

7. Consider a random graph G on n vertices where for each pair of vertices u, v, there is
an edge (u, v) with probability p ∈ [0, 1]. What is the expected number of cycles of
length 3 in this graph?
( )
(a) n3 · p3
p3
(b)
(n3 )
(c) n3 p3
(d) None of the above

3

(n)
Answer: (a) 3
· p3
( )
There are n3 unordered triples of vertices. The probability that(each
) such vertex set
forms a triangle is p3 . Thus the expected number of triangles is n3 · p3 . ⊣

The next two questions refer to the following two functions.

int f(int m) { int g(int m) {
int a, b, c, d; int a = 1;
a = 0; b = 0; int i = 0;
c = 0; d = 1; while (i < m) {
while (a < m) { i = i+1;
a = a + 1; a = 2*a;
b = b + c; }
int temp = d; return a;
d = c; }
c = temp;
}
return b;
}
8. What is the result of f(100)?

(a) 100
(b) 5050
(c) 50
(d) 1

Answer: (c) 50

The value of the pair (c, d) flips between (0, 1) and (1, 0) in each iteration of the while
loop in f, starting with (0, 1). In each iteration, we add 1 to a, and c to b. Thus the
sequence of values taken by (a, b) at the end of each iteration is:

(1, 0), (2, 1), (3, 1), (4, 2), ..., (98, 49), (99, 49), (100, 50).

Hence the value of b when the loop exits is 50. In general, f (n) = ⌊ n2 ⌋. ⊣

9. If g(f(n)) = 32, which of the following is a possible value of n?

(a) 8
(b) 11
(c) 5
(d) 64

4

Answer: (b) 11

At the start of each iteration of the loop in g, we maintain the invariant that a = 2i .
If a = 32 when the loop exits, it means that i = 5. Since 5 = f (n), it has to be the
case that n = 10 or n = 11. The only choice that fits is (b). ⊣

10. What can you conclude from the following statements about problems A and B?

(I) There is a polynomial-time algorithm to solve A.
(II) There is an exponential-time algorithm to solve B.
(III) B can be reduced to A in polynomial-time.

(a) Not all of them can be simultaneously true.
(b) There is a polynomial-time algorithm for B.
(c) A cannot be reduced to B in polynomial-time.
(d) There is no exponential-time algorithm for A.

Answer: (b) There is a polynomial-time algorithm for B.

If B can be reduced to A and A has a PTIME algorithm, clearly B also has a PTIME
algorithm, so (b) is true.
We cannot assert (a), since B can have both an EXPTIME algorithm and a PTIME
algorithm. Since B has a PTIME algorithm, one can reduce A to B in PTIME, so we
cannot assert (c). We cannot assert (d), since there can be many inefficient algorithms
for A, apart from the efficient PTIME algorithm. ⊣

5

Part B
1. A Muller automaton is defined as a tuple M = (Q, I, Σ, →, T ) where:

• Q is a finite set of states;
• I ⊆ Q is the set of initial states;
• Σ is the finite alphabet;
• →⊆ Q × Σ × Q is the transition relation; and
• T ⊆ 2Q is the accept table.

A run of M on a word x = a1 . . . an is a sequence of the form ρ = q0 a1 q1 · · · qn−1 an qn
ai
where q0 ∈ I and qi−1 − → qi for each i ≤ n. For a run ρ as above, we define vs(ρ) =
{q0 , . . . , qn }, the set of visited states along the run ρ. We say that M accepts a word
x if there is a run ρ of M on x such that vs(ρ) ∈ T . The language accepted by M ,
denoted L(M ), is the set {x ∈ Σ∗ | x is accepted by M }.
Consider the Muller automaton whose states and transitions are depicted below. The
initial state is {q0 }.

q0

a b
b
a qa qb b
a

(a) Consider the run ρ1 = q0 aqa aqa bqb on the word aab. What is vs(ρ1 )? Now,
consider the run ρ2 = q0 bqb bqb on the word bb. What is vs(ρ2 )?
(b) What is the language accepted by the above automaton when the accept table is
{{q0 , qa , qb }}?
(c) What should the accept table be in order to accept a∗ ?

Answer:

(a) vs(ρ1 ) = {q0 , qa , qb } and vs(ρ2 ) = {q0 , qb }.
(b) We see that the automaton goes to state qa exactly when it reads the letter a
and goes to state qb exactly when it reads b. The language is thus the set of all
words which have at least one occurrence of a and at least one occurrence of b.
(c) By the logic above, the accept table should be {{q0 }, {q0 , qa }}.

⊣

2. Consider the language L over the alphabet {a, b} given below.

L = {w | w has equal number of a’s and b’s, and there are no adjacent a’s.}

For instance, the words abba, abab are in the language but not bab and baab.

6

(a) Prove that L does not contain any word that starts and ends with a b.
(b) Give a context-free grammar for L.

Answer:

(a) Suppose, for the sake of contradiction, that L contains a word bub. Since bub has
equal number of a’s and b’s, u contains two more a’s than b’s. Let u have n + 2
a’s and n b’s, for some natural number n. There are n + 1 gaps betweens the a’s.
Mapping n b’s to these gaps will leave at least one gap vacant, and thus there
are two adjacent a’s in u. This contradicts the assumption that bub ∈ L.
(b)

S → Sab | Sba | Sab Sba | ε
Sab → aSba b | Sab Sab | ab
Sba → bSab a | Sba Sba | ba

The intuition is that Sab generates words from L which start with an a and ends
with a b. Similarly for Sba . We ensure that concatenation of the form Sba Sab is
not be allowed, to avoid consecutive occurrences of a.

⊣

3. We say that an integer a is co-prime to another integer b if gcd(a, b) = 1. For any
integer n, φ(n) is the number of integers from 1 up to |n| that are co-prime to n.

(a) Calculate φ(5), φ(10) and φ(20).
(b) Show that φ(p) = p − 1 for any prime p.
(c) Prove that if a is co-prime to b then the remainder of a when divided by b is also
co-prime to b.

Answer:

(a) φ(5) = 4, since 1, 2, 3, 4 are all co-prime to 5. φ(10) = 4, since 1, 3, 7, 9 are
co-prime to 10. φ(20) = 8, since 1, 3, 7, 9, 11, 13, 17, 19 are co-prime to 20.
(b) If p is prime, gcd(a, p) = 1 for all a < p. Thus φ(p) = p − 1.
(c) Observe that gcd(a mod b, b) = gcd(a, b). If gcd(a, b) = 1 then gcd(a mod b, b) =
1 as well. Thus the remainder of a when divided by b is also co-prime to b.

⊣

4. You are organizing a party involving 2n diplomats. Each pair of diplomats are either
friends or enemies. You have managed to invite an excellent set of guests, each of
whom has more friends than enemies (among the other guests). Can you now seat
them at a round table so that everyone has two friends as their neighbours. (Hint:
Model this situation as an appropriate graph so that the desired seating arrangement
is a Hamiltonian path.)

7

Answer: Let the wizards be numbered 1, . . . , 2n. Form a graph G = (V, E) with V =
{1, . . . , 2n} and E = {(i, j) | i and j are friends}. Treat the edges to be undirected.
Since each wizard has more friends than enemies, it means that the degree of each
vertex in G is at least n. If we find a Hamiltonian cycle in this graph, we can seat
wizards around the table so that each wizard has friends on both sides. By Dirac’s
Theorem, We know that a Hamiltonian cycle always exists for such graphs. A proof
of this fact can be found here. ⊣

5. For any set S of natural numbers, we say that a relation R ⊆ S × S is a 2-spanner of
S if it satisfies the following conditions:

• (i, j) ∈ R ⇒ i < j;
• i < j ⇒ [((i, j) ∈ R) or (∃k : (i, k) ∈ R ∧ (k, j) ∈ R)].

For example, {(1, 2), (2, 3)} is a 2-spanner for {1, 2, 3}, and

R1 = {(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5), (4, 6), (4, 7), (5, 6), (6, 7)}

is a 2-spanner for S = {1, . . . , 7}. There are other 2-spanners for S, of course. R2 =
{(i, j) | i, j ∈ {1, . . . , 7}, i < j} is an example. But R1 is of size 10, while R2 is of size
21. We would like to find 2-spanners that are as small as possible.

(a) Suppose you are given 2-spanners R1 and R2 for {1, . . . , 7} and {9, . . . , 15} re-
spectively, each of size 10. Use them to construct a 2-spanner R for {1, . . . , 15}.
Try to get R of size 34.
(b) Generalize the above construction to show that any set S of size 2k −1 (for k > 2)
has a 2-spanner of size (k − 2)2k + 2.

Answer: For k > 0, let S(k) = {1, . . . , 2k − 1}. W.l.o.g. we will construct 2-spanners
for S(k). That can be adapted to any S of size 2k − 1. Let T (k) denote the size of the
minimal 2-spanner for S(k).
For S(1) = {1}, the 2-spanner is ∅, of size 0.
For S(2) = {1, 2, 3}, the 2-spanner is {(1, 2), (2, 3)}, of size 2.
For S(3) = {1, . . . , 7}, we have already shown a 2-spanner of size 10 = (3 − 2)23 + 2.
For k > 3, assume there are 2-spanners R1 and R2 of size T (k − 1) = (k − 3)2k−1 + 2
for {1, . . . , 2k−1 − 1} and {2k−1 + 1, . . . , 2k − 1}. Form R by adding the pairs (i, 2k−1 )
for all i < 2k−1 and the pairs (2k−1 , j) for j > 2k−1 to R1 ∪ R2 . The number of such
pairs is 2(2k−1 − 1) = 2k − 2. So we have

T (k) = 2T (k − 1) + 2k − 2
= 2[(k − 3)2k−1 + 2] + 2k − 2
= (k − 3)2k + 4 + 2k − 2
= (k − 2)2k + 2

⊣

8

6. There is a treasure hunt game in which parts of a treasure are hidden across n islands,
numbered 1 to n. You start in island 1, and aim to collect all parts of the treasure, by
hopping from island to island. Each island has a list of other islands you can directly
go to. (Note that if you can directly go from island i to island j, it does not necessary
mean that you can directly go from j to i.) You can revisit the same island multiple
times during your search. Design an algorithm that takes as input the number n of
islands, the n neighbourhood lists, and determines if you can succeed in collecting all
parts of the treasure. The algorithm should run in time O(n2 · 2n ).

Answer: Let I = {1, . . . , n}. Consider a graph G where the nodes are pairs (S, i),
where S ⊆ {1, . . . , n}, and there is an edge from (S, i) to (S ′ , j) if S ′ = S ∪ {j} and j
is a neighbour of i. The question amounts to asking if there is some j such that (I, j)
is reachable from ({1}, 1) in G, and can be solved using BFS in time O(|V | + |E|).
The number of vertices in the graph is n.2n and the number of edges is |E|.2n (if j is
a neighbour of i, we have an edge from (S, i) to (S ∪ {j}, j) for each S ⊆ {1, . . . , n}).
Since |E| ≤ n2 , a naive algorithm for reachability runs in time O(n2 · 2n ).
An alternate solution, with better complexity is as follows. Consider a graph G′ with
vertices {1, . . . , n} and edges given by the neighbourhood lists. This is the graph
mapping the islands and the paths between them. Decompose G′ into SCCs in O(n2 )
time. These SCCs will be connected as a DAG H ′ (each SCC will be a vertex in this
DAG). There is a way to collect all parts of the treasure iff there is a path in H ′ that
visits all the vertices. In other words, there is a solution iff the longest path in the
DAG H ′ equals the number of nodes in H ′ . Longest paths in DAGs can be found in
linear time. Hence the overall complexity comes to O(n2 ). ⊣

7. Consider the following inventory problem. You are running a company that sells
lorries. Predictions tell you the quantity of sales to expect over the next n months.
Let di denote the number of sales expected in month i. We assume that sales happen
on the first of the month, and that lorries not sold are stored till the start of the
next month. You can store at most C lorries, and it costs R to store each lorry for
a month. You receive lorries from the manufacturer in shipments, each of which has
a transportation fee of F (regardless of the number of lorries ordered). You start out
with no lorries. Your aim is to place orders (say li is the number of lorries ordered in
month i) so as to satisfy the following constraints:

• For each i, the number of lorries on hand at the start of month i (li + whatever
is stored from the previous month) is enough to meet the demand di .
• For each i, the number of lorries left over after meeting the demand di should
not exceed the storage capacity C.

The aim is to determine the orders (l1 , . . . , ln ) that will minimize the overall trans-
portation fee and the overall storage cost.
For example, if n = 4, and the demands for each month is given by 10, 11, 8, 12, and
if F = 50, while R = 2 and C = 10, then here are a few possible scenarios.

9

Month 1 2 3 4 Total
di 10 11 8 12
li 10 11 8 12
Cost 50 50 50 50 200
li 20 11 0 10
Cost 50 + 10 × 2 50 + 10 × 2 2×2 50 194
li 10 19 0 12
Cost 50 50 + 8 × 2 0 50 166

Let ci (S) denote the minimal cost of transportation and storage to meet demands from
month i till month n, given that we have S lorries left over at the start of month i,
while satisfying the storage requirements.

(a) Write an expression for cn (S).
(b) Express ci (S) in terms of ci+1 (S ′ ) for appropriate values of S ′ .
(c) Convert the above equations into a dynamic programming algorithm that com-
putes c1 (0). Your algorithm must run in time polynomial in n and C.

Answer: Let ci (S) be the optimal cost of ordering lorries for the rest of the semester
starting from month i, given a stock of S of lorries left over. We need to finally
compute c1 (0).
The recurrence for ci (S) can be derived as follows. You can order anywhere from
j = di − S to j = di + C − S pieces this month. If we order j pieces, the cost incurred
is F (the delivery fee) + R(j + S − di ) + ci+1 (j + S − di ). So we take minimum over all
possible values of j. The base case is cn (S) = F (there is no storage till next month,
so only the delivery fee is incurred) if S ≥ dn , and cn (S) = 0 otherwise.


F + minj=di (R(j + S − di ) + ci+1 (j + S − di )) if i < n
di +C−S

ci (S) = F if i = n and S ≥ dn


0 otherwise

The ci (S) values can be systematically computed by filling in a suitable array that
stores the values of the recursive calls. ⊣

10