CMI Entrance Exam 2021 Question Paper for M.Sc or PhD Computer Science

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

This question paper consists of two parts. The total marks are 100.

• Part A has 10 questions of 3 marks each. Each question in Part A has four choices,
of which exactly one is correct. Answers to Part A must be entered directly on the
computer.

• Part B has 7 questions of 10 marks each. Answers to Part B must be written in the
designated place in the answer booklet provided to you.

• There are separate sheets at the end of the answer booklet for rough work.

Part A
1. If the milkman doesn’t deliver milk or the geyser doesn’t work, then Akash will be
late for school and lunch will be cooked late. Suppose lunch was actually cooked on
time. Which of the following is definitely true?
(a) Akash was late for school (b) Akash reached school in time
(c) Geyser worked (d) Milkman did not deliver milk
2. Let L be the language over {a, b} that contains the same number of occurrences of a
and b. Which of the following languages is regular?
(a) L ∩ a∗ b∗ (b) (L ∩ a∗ b∗ ) ∪ a∗ b∗
(c) L ∪ a∗ b∗ (d) (L ∩ a∗ b∗ ) ∪ b∗ a∗
3. Which of the following regular expressions represents binary strings that are multiples
of 3? Note that we consider the leftmost bit to be the most significant.
(a) ((11)0∗ )∗ (b) (10∗ )∗
(c) 1(01∗ )∗ (d) (11 + 101∗ 01 + 0)∗
4. Consider the following statements about finite simple graphs G:

(i) If each vertex of a graph G has degree at least 2 then G contains a cycle as a
subgraph.
(ii) If the number of edges of a graph G is at least as large as the number of its
vertices, then G contains a cycle as a subgraph.

Which of the above two statements holds for all graphs?
(a) (i) only (b) (ii) only
(c) both (i) and (ii) (d) neither of them

1

5. One day, Dumbledore assigns Harry Potter the task of obtaining the Philosopher’s
Stone that lies in an inner chamber surrounded by many rooms. To guide him along,
he is given the Marauder’s Map which contains the following graph

Harry wishes to color every wall with colors such that walls that meet at a corner
get different colors. Harry also wishes to color every room so that adjacent rooms get
different colors. What is the minimum number of colors to accomplish this?

(a) 4 colors for walls and 4 colors for the rooms
(b) 3 colors for walls and 4 colors for the rooms
(c) 2 colors for walls and 3 colors for the rooms
(d) 2 colors for walls and 5 colors for the rooms

6. In the chamber containing the Philosopher’s stone, Harry sees a deck of 5 cards, each
with a distinct number from 1 to 5. Harry removes two cards from the deck, one at
time. What is the probability that the two cards selected are such that the first card’s
number is exactly one more than the number on the second card?
(a) 1/5 (b) 4/25
(c) 1/4 (d) 2/5
7. You are given a sequence of letters x1 x2 . . . xn where each xi ∈ {a, b, c, d, e, f, g, h}.
You can form a new sequence from the given sequence as follows. Start with x1 . Place
xm+1 either to the left or to the right of the sequence already built from x1 x2 . . . xm .
For instance, from dcbeb you can form ecdbb through the steps d → cd → cdb →
ecdb → ecdbb and bbcde through the steps d → cd → bcd → bcde → bbcde.
What is the largest sequence in lexicographic (dictionary) order that you can form
from the input sequence becgdfg?
(a) ggebcdf (b) ggfedcb (c) ggecbdf (d) ggfebcd

8. There is a basket full of apples, oranges, mangoes, pears and pomegranates. You want
to pick three fruits from the basket. Multiple pieces of the same fruit can be picked.
However, if you pick mangoes, you cannot pick apples.
In how many ways can you pick three fruits satisfying this condition?
(a) 14 (b) 40 (c) 28 (d) 20

2

The next two questions refer to the following procedure.

The procedure operates on three arrays A[0..99], B[0..99] and C[0..99], which are
initialized with integer values.

procedure mystery() {
for (i = 0; i < 100; i++) { C[i] = A[i]; }
p = 99;
for (i = 0; i < 100; i++) {
B[p] = C[0];
p = p-1;
for (j = 1; j < 100; j++) {
C[j-1] = C[j];
}
}
}

9. When the procedure terminates, which of the following statements can be asserted
about the array B?

(a) All elements of B are equal to A[0]
(b) B contains the elements of A sorted in descending order
(c) All values of B are the same
(d) B contains the elements of A in reverse order

10. When the procedure terminates, which of the following statements can be asserted
about the array C?

(a) It contains the elements of A sorted in ascending order
(b) It contains the elements of A sorted in descending order
(c) All values are equal to A[99]
(d) All values are equal to A[0]

3

Part B
√ √ √ √
1. Let A = ( 3 + 2)1000 , B = ( 3 − 2)1000 . Prove the following statements.

(a) A + B is an integer.
(b) The digit immediately after the decimal point in B is 0.
(c) The digit immediately after the decimal point in A is 9.
(d) Both A, B are irrational.

2. Imagine you are playing a computer game that consists of different types of coins.
You have the power to cast two magic spells s1 and s2 . Each spell consumes some
number of coins of each type and produces some number of coins of each type. Spell
s1 consumes one coin of type t1 and produces two coins of type t2 , written in short as
(−1 t1 , +2 t2 ). Spell s2 is (−1 t2 , +1 t1 ). You are allowed to cast the two spells any
number of times, but a spell cannot be cast if there aren’t enough coins present for
consumption. For example, s2 cannot be cast if there are 0 coins of type t2 .

(a) Suppose you start with n coins of type t1 and 0 coins of type t2 . If you repeatedly
cast spell s1 till it can no longer be cast, what is the total number of coins (of
both types) at the end?
(b) Suppose you start with n coins of type t1 and 0 coins of type t2 . You are allowed
to cast both the spells s1 and s2 . Give a sequence of spells that will lead you to
4n total coins. Can you extend the sequence to produce more than 4n coins?
(c) Suppose we provide you with a third type of coin t3 , and you start with n coins
of type t1 and 0 coins of types t2 and t3 . Come up with a new spell s3 satisfying
the following three properties:
• Spell s3 can add or remove atmost two coins of any type.
• Using spells s1 and s3 repeatedly in some order, you can reach 4n total coins.
• There is no sequence of spells using only s1 and s3 that can produce more
than 4n total coins.

3. A cut edge of a connected graph G is any edge e = {u, v} of G such that the graph
G − e obtained by deleting edge e (and not deleting u or v) is disconnected. In fact,
G − e will have exactly two connected components. Let G be an arbitrary finite simple
connected graph in which every vertex has an odd degree, and let e be an arbitrary
cut edge of G. Let H1 , H2 be the two connected components of G − e.
Prove or disprove the following statement: Each of H1 , H2 must necessarily have an
odd number of vertices.
To disprove this statement it suffices to exhibit a graph which contradicts the state-
ment. A proof must take the form of an argument.

4. For a language L over an alphabet Σ, define

SW(L) := { y ∈ Σ∗ | ∃x ∈ Σ∗ s.t. xyx ∈ L}

Prove that if L is regular, SW(L) is also regular.

4

5. Given a list A of N elements and a number K, your task is to output the N − K + 1
values listing the minimum among A[i] · · · A[i + K − 1] for every 1 ≤ i ≤ N − K + 1.
Provide an algorithm for this task, that runs in time atmost O(N log K).

6. Let A = A[1]A[2] · · · A[n] be an array of n numbers where n = 2k − 1 for some k > 0.
Consider a binary tree T built from the array in the following manner. The root of
T is the middle element of A. Let AL and AR denote the left and right subarrays
resulting from the removal of the middle element from A. The left and right subtrees
of the root node are binary trees defined similarly on AL and AR , respectively.
Each element A[i] of the array is a node in this tree T . Let Si denote the indices
occurring in the unique path from the root node to the element A[i]. We say that
index i is good if for every j1 , j2 in Si with j1 < j2 , we have A[j1 ] ≤ A[j2 ].
Prove that the subarray A[i1 ]A[i2 ] · · · A[im ] consisting only of good indices is sorted.

7. Consider the functions foo and bar described in pseudocode below, where // denotes
quotient (integer division) and % denotes remainder.

int foo(int n) {
int i = 1;
while (bar(i) < n) {
i = 2*i;
}
return(i);
}

int bar(int n) {
if (n == 0) {
return(1);
}
int x = bar(n // 2);
if (n % 2 == 0) {
return(x*x);
} else {
return(2*x*x);
}
}

(a) What function does bar(n) compute? Justify your answer.
(b) If foo(n) computes x, how do n and x relate to each other. Justify your answer.
(c) How many recursive calls to bar are made in a computation of foo(100)?

5