CMI Entrance Exam 2019 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 2019
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 given in the special answer sheet provided for it. Answers to Part
B must be written only in the designated space after the corresponding question.

Part A
1. Let L1 := { an bm | m, n ≥ 0 and m ≥ n } and L2 := { an bm | m, n ≥ 0 and m < n }.
The language L1 ∪ L2 is:
(a) regular, but not context-free (b) context-free, but not regular
(c) both regular and context-free (d) neither regular nor context-free
2. Let A be an NFA with n states.Which of the following is necessarily true?

(a) The shortest word in L(A) has length at most n−1.
(b) The shortest word in L(A) has length at least n.
(c) The shortest word not in L(A) has length at most n−1.
(d) The shortest word not in L(A) has length at least n.

3. Suppose that the figure to the right
is a binary search tree. The letters A
indicate the names of the nodes, not
the values that are stored. What
B C
is the predecesor node, in terms of
value, of the root node A?
D E F G
(a) D

(b) H H I J K L

(c) I

(d) M M N

4. There are five buckets, each of which can be open or closed. An arrangement is a
specification of which buckets are open and which are closed. Every person likes some
of the arrangements and dislikes the rest. You host a party, and amazingly, no two
people on the guest list have the same likes and dislikes. What is the maximum number
of guests possible?
5
(b) 52


(a) 52 (c) 25 (d) 22
5. Let π = [x1 , x2 , . . . , xn ] be a permutation of {1, 2, . . . , n}. For k < n, we say that π
has its first ascent at k if x1 > x2 . . . > xk and xk < xk+1 . Home many permutations
have their first ascent at k?
(a) nk - (k+1)n
(b) n! n! n! n! n n





k!
− (k+1)! (c) (k+1)! − (k+2)! (d) (k+1) - (k+2)

1

6. Suppose you alternate between throwing a normal six-sided fair die and tossing a fair
coin. You start by throwing the die. What is the probability that you will see a 5 on
the die before you see tails on the coin?
1
(a) 12 (b) 16 (c) 29 (d) 27
7. An interschool basketball tournament is being held at the Olympic sports complex.
There are multiple basketball courts. Matches are scheduled in parallel, with staggered
timings, to ensure that spectators always have some match or other available to watch.
Each match requires a team of referees and linesmen. Two matches that overlap
require disjoint teams of referees and linesmen. The tournament organizers would
like to determine how many teams of referees and linesmen they need to mobilize to
effectively conduct the tournament. To determine this, which graph theoretic problem
do the organizers have to solve?

(a) Find a minimal colouring.
(b) Find a minimal spanning tree.
(c) Find a minimal cut.
(d) Find a minimal vertex cover.

8. We have constructed a polynomial time reduction from problem A to problem B.
Which of the following is not a possible scenario?

(a) We know of polynomial time algorithms for both A and B.
(b) We only know of exponential time algorithms for both A and B.
(c) We only know an exponential time algorithm for A, but we have a polynomial
time algorithm for B.
(d) We only know an exponential time algorithm for B, but we have a polynomial
time algorithm for A.

The next two questions refer to the following program.

In the code below reverse(A,i,j) takes an array A, indices i and j with i ≤ j, and re-
verses the segment A[i], A[i+1],. . . ,A[j]. For instance if A = [0,1,2,3,4,5,6,7] then,
after we apply reverse(A,3,6), the contents of the array will be A = [0,1,2,6,5,4,3,7].

function mystery (A[0..99]) {
int i,j,m;
for (i = 0; i < 100; i++) {
m = i;
for (j = i; j < 100, j++) {
if (A[j] > A[m]) {
m = j;
}
}
reverse(A,i,m);
}
return;
}

2

9. When the procedure terminates, the array A has been:
(a) Sorted in descending order (b) Sorted in ascending order
(c) Reversed (d) Left unaltered
10. The number of times the test A[j] > A[m] is executed is:
(a) 4950 (b) 5050 (c) 10000 (d) Depends on the contents of A

3

Part B
Answers to Part B must be written only in the designated space after the corresponding
question.

1. Consider an alphabet Σ = {a, b}.
Let L1 be the language given by the regular expression (a + b)∗ bb(a + b)∗ and let L2
be the language baa∗ b.
Define L := {u ∈ Σ∗ | ∃w ∈ L2 s.t. uw ∈ L1 }.

(a) Give an example of a word in L.
(b) Give an example of a word not in L.
(c) Construct an NFA for L.

4

5

2. Let us assume a binary alphabet Σ = {a, b}. Two words u, v ∈ Σ∗ are said to be
conjugates if there exist w1 , w2 ∈ Σ∗ such that u = w1 w2 and v = w2 w1 . Prove that u
and v are conjugates if and only if there exists w ∈ Σ∗ such that uw = wv.

6

7

3. There is a party of n people. Each attendee has at most r friends in the party. The
friend circle of a person includes the person and all her friends. You are required to
pick some people for a party game, with the restriction that at most one person is
picked from each friend circle. Show that you can pick r2n+1 people for the game.

8

9

4. Consider the assertion: Any connected undirected graph G with at least two vertices
contains a vertex v such that deleting v from G results in a connected graph.
Either give a proof of the assertion, or give a counterexample (thereby disproving the
assertion).

10

11

5. In the land of Twitter, there are two kinds of people: knights (also called outragers),
who always tell the truth, and knaves (also called trolls), who always lie. It so hap-
pened that a person with handle @anand tweeted something offensive. It was not
known whether @anand was a knight or a knave. A crack team, headed by Inspector
Chitra, rounded up three suspects and interrogated them.
The first interrogation went as follows.

Chitra : What do you know about @anand?
Suspect 1 : @anand once claimed that I was a knave.
Chitra : Are you by any chance @anand?
Suspect 1 : Yes.

The second interrogation:

Chitra : Have you ever claimed you were @anand?
Suspect 2 : No.
Chitra : Did you ever claim you are not @anand?
Suspect 2 : Yes.

The third suspect arrived with a defense lawyer (also on Twitter):

Lawyer : My client is indeed a knave, but he is not @anand.
Suspect 3 : My lawyer always tells the truth.

Which of the above suspects are innocent, and which are guilty? Explain your reason-
ing.

12

13

6. Let A be an n×n matrix of integers such that each row and each column is arranged in
ascending order. We want to check whether a number k appears in A. If k is present,
we should report its position—that is, the row i and column j such that A(i, j) = k.
Otherwise, we should declare that k is not present in A.

(a) Describe an algorithm that solves this problem in time O(n log n). Justify the
complexity of your algorithm.
(b) Describe an algorithm that solves this problem by examining at most 2n values in
A. Justify the complexity of your algorithm.
(c) For both algorithms, describe a worst-case input where k is present in A.

14

15

7. A college professor gives several quizzes during the semester, with negative marking.
He has become bored of the usual “Best M out of N quizzes” formula to award marks
for internal assessment. Instead, each student will be evaluated based on the sum of
the best contiguous segment (i.e., no gaps) of marks in the overall sequence of quizzes.
However, the student is allowed to drop upto K quizzes before calculating this sum.
Suppose a student has scored the following marks in 10 quizzes during the semester.

Quiz 1 2 3 4 5 6 7 8 9 10
Marks 6 −5 3 −7 6 −1 10 −8 −8 8

Without dropping any quizzes, the best segment is quiz 5-7, which yields a total of 15
marks. If the student is allowed to drop upto 2 quizzes in a segment, the best segment
is quiz 1-7, which yields a total of 24 marks after dropping quizzes 2 and 4. If the
student is allowed to drop upto 6 quizzes in a segment, the best total is obtained by
taking the entire list and dropping all 5 negative entries, yielding 33 marks.
For 1 ≤ i < N , 0 ≤ j ≤ K, let B[i][j] denote the maximum sum segment ending at
position i with at most j marks dropped.

(a) Write a recursive formula for B[i][j].
(b) Explain how to calculate, using dynamic programming, the score the professor
needs to award each student.
(c) Describe the space and time complexity of your dynamic programming algorithm.

16

17

18