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

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

This question paper has 4 printed sides. Part A has 10 questions of 3 marks each. 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. Which of the words below matches the regular expression a(a + b)∗ b + b(a + b)∗ a?
(a) aba (b) bab (c) abba (d) aabb

2. Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan
attend, then Deepa will attend too. If Bharani does not attend, then Akash will not
attend. If Deepa does not attend, which of the following is true?
(a) Chetan does not attend (b) Akash does not attend
(c) either (a) or (b) (d) none of the above
3. In a running race, Geetha finishes ahead of Shalini and Vani finishes after Aparna.
Divya finishes ahead of Aparna. Which of the following is a minimal set of additional
information that can determine the winner?

(a) Geetha finishes ahead of Divya and Vani finishes ahead of Shalini.
(b) Aparna finishes ahead of Shalini.
(c) Divya finishes ahead of Geetha.
(d) None of the above.

4. Let G = (V, E) be an undirected simple graph, and s be a designated vertex in G. For
each v ∈ V , let d(v) be the length of a shortest path between s and v. For an edge
(u, v) in G, what can not be the value of d(u) − d(v)?
(a) 2 (b) -1 (c) 0 (d) 1

5. How many paths are there in the plane from (0, 0) to (m, n) ∈ N × N, if the possible
steps from (i, j) are either (i + 1, j) or (i, j + 1)?
(a) 2m m m+n




n
(b) n
(c) n
(d) mn

6. You are given two coins A and B that look identical. The probability that coin A
turns up heads is 41 , while the probability that coin B turns up heads is 43 . You choose
one of the coins at random and toss it twice. If both the outcomes are heads, what is
the probability that you chose coin B?
1
(a) 16 (b) 12 9
(c) 16 9
(d) 10

7. Let Cn be the number of strings w consisting of n X’s and n Y ’s such that no initial
segment of w has more Y ’s than X’s. Now consider the following problem. A person
stands on the edge of a swimming pool holding a bag of n red and n blue balls. He
draws a ball out one at a time and discards it. If he draws a blue ball, he takes one

1

step back, if he draws a red ball, he moves one step forward. What is the probability
that the person remains dry?
Cn Cn n · Cn n · Cn
(a) 2n (b) 2n
(c) (d) 2n

2 n
(2n)! n

8. There are 7 switches on a switchboard, some of which are on and some of which are
off. In one move, you pick any 2 switches and toggle each of them—if the switch you
pick is currently off, you turn it on, if it is on, you turn it off. Your aim is to execute
a sequence of moves and turn all 7 switches on. For which of the following initial
configurations is this not possible? Each configuration lists the initial positions of the
7 switches in sequence, from switch 1 to switch 7.
(a) (off,on,off,on,off,off,on) (b) (off,on,on,on,on,on,off)
(c) (on,off,on,on,on,on,on) (d) (off,off,off,off,off,on,off)
9. Your college has sent a contingent to take part in a cultural festival at a neighbouring
institution. Several team events are part of the programme. Each event takes place
through the day with many elimination rounds. Your contingent is multi-talented
and each individual has the skills to take part in a subset of the events. However,
the same individual cannot be part of the team for two different events because of a
possible clash in timings. Your aim is to create teams to take part in as many events
as possible.
To do this, you decide to model the problem as a graph where the nodes are the
events and edges represent pairs of events where the team that you plan to send
shares a member. In this setting, the graph theoretic question to be answered is:

(a) Find a maximum length simple cycle
(b) Find a maximum size independent set
(c) Find a maximum matching
(d) Find a maximal connected component

10. What does the following function compute in terms of n and d, for integer values of n
and d, d > 1? Note that a//b denotes the quotient (integer part) of a ÷ b, for integers
a and b. For instance 7//3 is 2.

function foo(n,d){
x := 0;
while (n >= 1) {
x := x+1;
n := n//d;
}
return(x);
}

(a) The number of ways of choosing d elements from a set of size n.
(b) The number of ways of rearranging d elements from a set of size n.
(c) The number of digits in the base d representation of n.
(d) The number of ways of partitioning n elements into groups of size d.

2

Part B
1. Consider the following non-deterministic finite automata (NFA) A1 and A2 :

a, b a, b

a b
A1 : q0 q1 A2 : p0 p1

(a) Give an example of a word which is accepted by both A1 and A2 .
(b) Give an example of a word which is accepted by A1 , but not by A2 .
(c) Draw the deterministic finite automaton (DFA) equivalent to A1 .

2. A student requests a recommendation letter from a professor. The professor gives
three sealed envelopes. Each envelope contains either a good recommendation letter
or a bad recommendation letter.

(a) Make a list of all the possible scenarios.
(b) Suppose now the professor tells the student that exactly one envelope contains
a good recommendation letter and the other two contain bad recommendation
letters. In the list of scenarios you prepared above, mark the ones that are still
possible.
(c) On envelope 1 is written the clue “This contains a bad recommendation letter”.
On envelope 2 is written the clue “This contains a bad recommendation letter”.
On envelope 3 is written the clue “Envelope 2 contains a good recommendation
letter”. Suppose now the professor gives the additional information that exactly
one of these three clues are true and the other two are false. Can the student find
out the contents of the envelopes without breaking their seals?

3. Let G be a simple graph on n vertices.
n−1


(a) Prove that if G has more than 2
edges then G is connected.
n−1


(b) For every n > 2, find a graph Gn which has exactly n vertices and 2
edges,
and is not connected.

4. You are given a sorted array of n elements which has been circularly shifted. For
example, {35, 42, 5, 12, 23, 26} is a sorted array that has been circularly shifted by 2
positions.
Give an O(log n) time algorithm to find the largest element in a circularly shifted
array. (The number of positions through which it has been shifted is unknown to
you.)

5. Let G = (V, E) be an undirected graph and V = {1, 2, . . . , n}. The input graph is
given to you by a 0 − 1 matrix A of size n × n as follows. For any 1 ≤ i, j ≤ n, the
entry A[i, j] = 1 if and only if (i, j) is an edge in G.
A connected component in G is a subgraph in which any two vertices are connected
to each other by paths. Give a simple algorithm to find the number of connected
components in G. Analyze the time taken by your procedure.

3

6. You are playing an old-style video game in which you have to shoot down alien spacec-
ships as they fly across the screen from left to right. Each spaceship flies across the
screen at a specified height. You have an antiaircraft gun set to shoot down all space-
ships at a certain height. Spaceships fly one at a time, so if your gun is set to fire at
the correct height, it will shoot down the spaceship currently flying across the screen.
You can set the initial height at which the gun fires. As the game progresses, you can
reset the height, but only to a lower value. You are given in advance the height at
which each spaceship flies. There are N spaceships numbered 1, 2, . . . , N in the order
in which they fly across the screen. For 1 ≤ i ≤ N , h[i] denotes the height at which
spaceship i flies.

(a) Let V [i] denote the maximum number of spaceships from i, i+1, . . . , N that you
can shoot down with a single gun. Write a recurrence for V [i] and describe a
strategy to compute V [i] using dynamic programming. What is the space and
time complexity of your solution?
(b) Describe an algorithm to compute the minimum number of guns required to shoot
down all the space ships. Each gun can be initialized separately to a firing height
and each gun can be separately reset to a lower value.

7. A First In First Out queue is a data structure supporting the operations Enque, Deque,
Print. Enque(x) adds the item x to the tail of the queue. Deque removes the element
at the head of the queue and returns its value. Print prints the head of the queue.

(a) You are given a queue containing 5 elements. Using a single additional temporary
variable X, write down a sequence of statements each being one of Enque, Deque,
Print so that the output of the program results in the 5 elements of the queue
being printed in reverse order.
(b) If the queue had n elements to begin with, how many statements would you need
to print the queue in reverse order?

4