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

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

This question paper has 5 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. In a connected undirected graph, the distance between two vertices is the number
of edges in the shortest path between them. Suppose we denote by P the following
property: there exists a vertex that is a neighbour of all other vertices. Consider the
following statements:

(i) If P is false, then there is a pair of vertices such that the distance between them
is at least 4.
(ii) If P is true, then the distance between any pair of vertices is at most 2.

What can you say about these statements?
(a) Only (i) is true. (b) Only (ii) is true.
(c) Both (i) and (ii) are true. (d) Neither (i) nor (ii) is true.
2. The symbol | reads as “divides”, and - as “does not divide”. For instance, 2 | 6 and
2 - 5 are both true. Consider the following statements:

(i) There exists a positive integer a such that (2 | (a3 − 1)) and (2 | a).
(ii) There exists a positive integer b such that 6 - (b3 − b).

What can you say about these statements?
(a) Only (i) is true. (b) Only (ii) is true.
(c) Both (i) and (ii) are true. (d) Neither (i) nor (ii) is true.
3. For a regular expression e, let L(e) be the language generated by e. If e is an expression
that has no Kleene star ∗ occurring in it, which of the following is true about e in
general?

(a) L(e) is empty.
(b) L(e) is finite.
(c) Complement of L(e) is empty.
(d) Both L(e) and its complement are infinite.

1

4. Consider a weighted undirected graph G with positive edge weights. Let (u, v) be an
edge in the graph. It is known that the shortest path from a vertex s to u has weight
53 and the shortest path from s to v has weight 65. Which of the statements is always
true?

(a) Weight of (u, v) ≤ 12.
(b) Weight of (u, v) = 12.
(c) Weight of (u, v) ≥ 12.
(d) Nothing can be said about the weight of (u, v).

5. A dodecahedron is a regular solid with 12 faces, each face being a regular pentagon.
How many edges are there? And how many vertices?
(a) 60 edges and 20 vertices. (b) 30 edges and 20 vertices.
(c) 60 edges and 50 vertices. (d) 30 edges and 50 vertices.
6. In the code fragment to the right, start and
end are integer values and prime(x) is a i := 0; j := 0; k := 0;
function that returns true if x is a prime for (m := start;
number and false otherwise. m <= end;
m := m+1){
At the end of the loop: if (prime(m)){
i := i + m;
(a) k == i-j. k := k - m;
}else{
(b) k == j-i.
j := j - m;
(c) k == -j-i. k := k + m;
}
(d) Depends on start and end. }

7. Varsha lives alone and dislikes cooking, so she goes out for dinner every evening. She
has two favourite restaurants, Dosa Paradise and Kababs Unlimited, to which she
travels by local train. The train to Dosa Paradise runs every 10 minutes, at 0, 10, 20,
30, 40 and 50 minutes past the hour. The train to Kababs Unlimited runs every 20
minutes, at 8, 28 and 48 minutes past the hour. She reaches the station at a random
time between 7:15 pm and 8:15 pm and chooses between the two restaurants based on
the next available train. What is the probability that she ends up eating in Kababs
Unlimited ?
1 1 2 1
(a) (b) (c) (d)
5 3 5 2
8. An advertisement for a tennis magazine states, “If I’m not playing tennis, I’m watching
tennis. And if I’m not watching tennis, I’m reading about tennis.” We can assume
that the speaker can do at most one of these activities at a time. What is the speaker
doing?
(a) Playing tennis. (b) Watching tennis.
(c) Reading about tennis. (d) None of the above.

2

9. ScamTel has won a state government contract to connect 17 cities by high-speed
fibre optic links. Each link will connect a pair of cities so that the entire network is
connected—there is a path from each city to every other city. The contract requires
the network to remain connected if any single link fails. What is the minimum number
of links that ScamTel needs to set up?
(a) 34 (b) 32 (c) 17 (d) 16

10. Which of the following relationships holds in general between the scope of a variable
and the lifetime of a variable (in a language like C or Java)?

(a) The scope of a variable is contained in the lifetime of the variable.
(b) The scope of a variable is the same as the lifetime of the variable.
(c) The lifetime of a variable is disjoint from the scope of the variable.
(d) None of the above.

Part B
1. A group of war prisoners are trying to escape from a prison. They have thoroughly
planned the escape from the prison itself, and after that they hope to find shelter
in a nearby village. However, the village (marked as B, see picture below) and the
prison (marked as A) are separated by a canyon which is also guarded by soldiers
(marked as S). These soldiers sit in their pickets and rarely walk; the range of view
of each soldier is limited to exactly 100 meters. Thus, depending on the locations
of soldiers, it may be possible to pass the canyon safely, keeping the distance to the
closest soldier strictly larger than 100 meters at any moment. The situation is depicted
in the following picture, where the circles around S indicate range of view.

S
S
A S B
S S
S

Provide an algorithm to determine if the prisoners can pass the canyon unnoticed,
given the width and the length of the canyon and the coordinates of every soldier in
the canyon, and assuming that soldiers do not change their locations. (Hint: Model
this as a graph, with soldiers represented by the vertices.)

3

2. A simple path (respectively cycle) in a graph is a path (respectively cycle) in which
no edge or vertex is repeated. The length of such a path (respectively cycle) is the
number of edges in the path (respectively cycle).
Let G be an undirected graph with minimum degree k ≥ 2.

(a) Show that G contains a simple path of length at least k.
(b) Show that G contains a simple cycle of length at least k + 1.

3. An undirected graph can be converted into a directed graph by choosing a direction
for every edge. Here is an example:

Show that for every undirected graph, there is a way of choosing directions for its
edges so that the resulting directed graph has no directed cycles.
4. Let Σ = {0, 1}. Let A, B be arbitrary subsets of Σ∗ . We define the following operations
on such sets:
A + B := { w ∈ Σ∗ | w ∈ A or w ∈ B }
A · B := { uv ∈ Σ∗ | u ∈ A and v ∈ B }
2A := { ww ∈ Σ∗ | w ∈ A }
Is it true that (A + B) · (A + B) = A · A + B · B + 2(A · B) for all choices of A and
B? If yes, give a proof. If not, provide suitable A and B for which this equation fails.
5. For a string x = a0 a1 · · · an−1 over the alphabet {0, 1, 2}, define val(x) to be the value
of x interpreted as a ternary number, where a0 is the most significant digit. More
formally, val(x) is given by X
3n−1−i · ai .
0≤i<n

Design a finite automaton that accepts exactly the set of strings x ∈ {0, 1, 2}∗ such
that val(x) is divisible by 4.
6. An automatic spelling checker works as follows. Given a word w, first check if w is
found in the dictionary. If w is not in the dictionary, compute a dictionary entry that
is close to w. For instance if the user types ocurrance, the spelling checker should
suggest occurrence, which belongs to the dictionary. Similarity between words such
as occurrence and occurance is quantified in terms of alignment.
An alignment between two strings w1 and w2 (over the alphabet {a, b, c, . . . , z}) is
obtained by inserting hyphens in the two strings such that the modified strings align
(i.e., the modified strings are of equal length, and at each position, either both strings
have the same letter or one of the strings has a hyphen).
Here are three examples of alignments. The first is between ocurrance and occurrence
and the second and third are between ctatg and ttaagc.

4

(1) oc-urr-ance (2) ct-at-g- (3) ctat---g-
occurre-nce -tta-agc ---ttaagc

A mismatch in an alignment is a position where one of modified strings has a hyphen
and the other does not. There are three mismatches in the first alignment given above,
five mismatches in the second, and seven mismatches in the third.
Use dynamic programming to give an efficient algorithm that takes two strings w1
and w2 (over the alphabet {a, b, c, . . . , z}) as its input, and computes the minimum
number of mismatches among all alignments of w1 and w2 . What is the running time
of your algorithm (in terms of the lengths of w1 and w2 )?

7. Consider the function M defined as follows:
(
n − 10 if n > 100
M (n) =
M (M (n + 11)) if n ≤ 100

(a) Compute the following.
i. M (101)
ii. M (99)
iii. M (87)
(b) Give a constant-time algorithm that computes M (n) on input n. (A constant-
time algorithm is one whose running time is independent of the input n.)

5