## CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2016)

Please wait while the activity loads.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

Question 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?

Only (i) is true. | |

Only (ii) is true. | |

Both (i) and (ii) are true. | |

Neither (i) nor (ii) is true. |

Question 1 Explanation:

If P is true, there is a “central” vertex that is a neighbor of all others. We can start from any vertex and reach any other by going via the center. So (ii) is true. There are graphs where P is false but the distance is at most 3 between any pair of vertices, so (i) is false.

Question 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 | (a

^{3}− 1)) and (2 | a). (ii) There exists a positive integer b such that 6 -| (b 3 − b). What can you say about these statements?Only (i) is true. | |

Only (ii) is true. | |

Both (i) and (ii) are true. | |

Neither (i) nor (ii) is true. |

Question 2 Explanation:

(i) is false. Note that (a

(ii) is false too. Note that (b

^{3}− 1) = (a − 1)(a^{2}+ a + 1), and hence 2 | a implies that both a − 1 and a^{2}+ a + 1 are odd, and hence so is their product. Thus 2 -| (a^{3}− 1).(ii) is false too. Note that (b

^{ 3}− b) = (b − 1)b(b + 1), and at least one of these factors is even and one is divisible by 3. Hence 6 | (b^{3}− b).Question 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?

L(e) is empty. | |

L(e) is finite. | |

Complement of L(e) is empty. | |

Both L(e) and its complement are infinite. |

Question 3 Explanation:

This is proved by a simple induction on the structure of the regular expression, using the fact that L(a) is finite for each letter a, and that unions and concatenations of finite languages are also finite.

Question 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?

Weight of (u, v) ≤ 12. | |

Weight of (u, v) = 12. | |

Weight of (u, v) ≥ 12. | |

Nothing can be said about the weight of (u, v). |

Question 4 Explanation:

If the weight of (u, v) is strictly less than 12, then there is a path from s to v of weight at most 53 + 11 = 64 (which goes from s to u and then takes the edge (u, v)). This contradicts the fact that the shortest path from s to v has weight 65. Thus the weight of (u, v) is at least 12.

Question 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?

60 edges and 20 vertices. | |

30 edges and 20 vertices. | |

60 edges and 50 vertices. | |

30 edges and 50 vertices. |

Question 5 Explanation:

Each face has five edges, and there are 12 faces. But each edge is shared between two faces. Thus the number of edges is (12 × 5)/2 = 30. The number of vertices is given by Euler’s formula to be |E| − |F | + 2 = 30 − 12 + 2 = 20.

Question 6 |

In the code fragment to the right, start and end are integer values and prime(x) is a function that returns true if x is a prime
number and false otherwise.
At the end of the loop:
i := 0; j := 0; k := 0;
for (m := start;
m <= end;
m := m+1){
if (prime(m)){
i := i + m;
k := k - m;
}else{
j := j - m;
k := k + m;
}
}

k == i-j. | |

k == j-i. | |

k == -j-i. | |

Depends on start and end. |

Question 6 Explanation:

The value of i + j + k is 0 initially, and also at the end of each iteration of the loop. Thus k = −j − i at the end of the loop.

Question 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/5 | |

1/3 | |

2/5 | |

1/2 |

Question 7 Explanation:

If she arrives in the intervals 7:20–7:28, 7:40–7:48, or 8:00–8:08, the next train goes to Kababs Unlimited. This adds up to 24 minutes, out of a total of 60 minutes, so (24/60) = (2/5)

Question 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?

Playing tennis. | |

Watching tennis. | |

Reading about tennis. | |

None of the above. |

Question 8 Explanation:

If he is not watching tennis, then he is reading about tennis. Which means he is not playing tennis, which implies that he is watching tennis. Thus, the assumption that he is not watching tennis leads to a contradiction. Therefore he is watching tennis.

Question 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?

34 | |

32 | |

17 | |

16 |

Question 9 Explanation:

If we connect the cities in a loop with 17 links, then even if any single link fails, we can connect the cities by traversing the loop the other way. If we only had 16 links connecting 16 cities, that would constitute a tree which would have only a single path between any pair of cities (and thus get disconnected by a single link failure).

Question 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)?

The scope of a variable is contained in the lifetime of the variable. | |

The scope of a variable is the same as the lifetime of the variable. | |

The lifetime of a variable is disjoint from the scope of the variable. | |

None of the above. |

Question 11 |

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.

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.)

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.)

Explanation |

Question 11 Explanation:

Consider a graph G = (V ∪ {N, S}, E) where V = {v

_{s}| s is a soldier}. N and S are two special vertices representing the north and south boundary of the canyon, respectively. For two soldiers s and s 0 , (v_{s}, v_{ s}0 ) ∈ E iff s and s 0 are at most 200 meters apart. For a soldier s, (v_{s}, N ) ∈ E iff s is at most 100 meters from the north boundary, and similarly (v_{s}, S) ∈ E iff s is at most 100 meters from the south boundary. It is clear that the prisoners cannot pass the canyon unnoticed iff there is a path between N and S. Thus it suffices to test reachability of S from N using any standard algorithm (for instance, one based on breadth-first search).Question 12 |

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.

Explanation |

Question 12 Explanation:

Build a path in the graph as follows:

Pick an arbitrary vertex v

Since the graph is finite, the above procedure terminates eventually. Let π = v

Let i be the least index such that v

Pick an arbitrary vertex v

_{1}in the first step. At each subsequent step, let v_{t}be the vertex picked last. If all neighbours of v_{ t}have already been picked, stop. Otherwise v_{ t+1}is chosen to be an arbitrary neighbour of v_{ t}hitherto unpicked.Since the graph is finite, the above procedure terminates eventually. Let π = v

_{1}· · · v_{ t}be the path produced at the end. By construction, it is a simple path. It follows that all neighbours of v_{t}have already been picked and they occur among {v_{1}, . . . , v_{ t−1}}. Since the minimum degree of the graph is k, it follows that k ≤ t − 1. Thus there are at least k + 1 vertices and hence at least k edges in π.Let i be the least index such that v

_{i}is adjacent to v_{t}. It is clear that the path from v_{ i}to v_{ t}is of length at least k. Adding the edge (v_{i}, v_{ t}) yields a simple cycle of length at least k + 1.Question 13 |

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.

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.

Explanation |

Question 13 Explanation:

Assign a distinct natural number N (v) to each vertex v of the graph. For an edge between v and w, choose the direction v → w provided N (v) < N (w). It is easy to prove that if there is a directed path from v to w in this scheme, then N (v) < N (w). Suppose there is a directed cycle involving v. This means that there is a directed path from v to itself, whence N (v) < N (v), which is a contradiction.

Question 14 |

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.

Explanation |

Question 14 Explanation:

The equation fails for A = {0} and B = {1}. In that case (A + B) · (A + B) = {00, 01, 10, 11}, whereas A · A + B · B + 2(A · B) = {00, 11, 0101}.

Question 15 |

For a string x = a

_{0}a_{1}· · · a_{ n−1}over the alphabet {0, 1, 2}, define val(x) to be the value of x interpreted as a ternary number, where a 0 is the most significant digit. More formally, val(x) is given by Design a finite automaton that accepts exactly the set of strings x ∈ {0, 1, 2} ∗ such that val (x) is divisible by 4.Explanation |

Question 15 Explanation:

Let L = {x ∈ {0, 1, 2} ∗ | val (x) is divisible by 4}. For any string x and b ∈ {0, 1, 2}:

(a) x ∈ L iff val (x) mod 4 = 0.

(b) if val (x) = i mod 4, val (xb) ≡ (3i + b) mod 4, for b = 0, 1, 2.

So to construct a DFA for L, it suffices to take 4 states q

(a) x ∈ L iff val (x) mod 4 = 0.

(b) if val (x) = i mod 4, val (xb) ≡ (3i + b) mod 4, for b = 0, 1, 2.

So to construct a DFA for L, it suffices to take 4 states q

_{0}, q_{ 1}, q_{ 2}, q_{ 3}, with q_{ i}recording the fact that the value of the string read so far is i mod 4. Under this interpretation, q_{0}will be the initial and (only) final state, and the automaton will transition from state q_{i}to q_{ j}on reading letter b ∈ {0, 1, 2}, where j = (3i + b) mod 4.Question 16 |

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 w 1 and w 2 (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.

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 x and y (over the alphabet {a, b, c, . . . , z}) as its input, and computes the minimum number of mismatches among all alignments of x and y. What is the running time of your algorithm (in terms of the lengths of x and y)?

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 w 1 and w 2 (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.

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 x and y (over the alphabet {a, b, c, . . . , z}) as its input, and computes the minimum number of mismatches among all alignments of x and y. What is the running time of your algorithm (in terms of the lengths of x and y)?

Explanation |

Question 16 Explanation:

Let x = a

This is reflected by the following recurrence :

opt(i, j) = min{opt(i − 1, j − 1) + c

where c

The following algorithm (which runs in O(mn) time) computes the minimum number of mismatches among alignments of x and y.

array A[0...m, 0...n]

array c[0...m, 0...n]

initialize A[i,0] = i for each i

initialize A[0,j] = j for each j

for j = 1,...,n

for i = 1,...,m

if a[i] == b[j] then c[i,j] = 0 else c[i,j] = 2

endfor

endfor

for j = 1,...,n

for i = 1,...,m

A[i,j] = min(A[i-1,j-1]+c[i,j], A[i-1,j]+1, A[i,j-1]+1)

endfor

endfor

return A[m,n]

_{1}a_{2}· · · a_{ m}and y = b_{1}b_{2}· · · b_{ n}. For any string w and any i ∈ {0, . . . , |w|}, we let w[. . . i] denote the prefix of w of length i. For i ∈ {0, . . . , m} and j ∈ {0, . . . , n}, we let opt(i, j) denote the minimum number of mismatches among all alignments of x[. . . i] and y[. . . j]. It is easy to see that opt(0, j) = j and opt(i, 0) = i. When i, j > 0, an optimal alignment of x[. . . i] and y[. . . j] either aligns x[. . . i − 1] with y[. . . j − 1] and tries to match a i and b j (if possible), or aligns y[. . . j] with x[. . . i − 1], leaving a i unmatched, or aligns x[. . . i] with y[. . . j − 1], leaving b j unmatched.This is reflected by the following recurrence :

opt(i, j) = min{opt(i − 1, j − 1) + c

_{ij}, opt(i − 1, j) + 1, opt(i, j − 1) + 1}.where c

_{ ij}denotes the cost of aligning a_{ i}(the string containing just the one letter) with b_{ j}. It is easy to see thatThe following algorithm (which runs in O(mn) time) computes the minimum number of mismatches among alignments of x and y.

array A[0...m, 0...n]

array c[0...m, 0...n]

initialize A[i,0] = i for each i

initialize A[0,j] = j for each j

for j = 1,...,n

for i = 1,...,m

if a[i] == b[j] then c[i,j] = 0 else c[i,j] = 2

endfor

endfor

for j = 1,...,n

for i = 1,...,m

A[i,j] = min(A[i-1,j-1]+c[i,j], A[i-1,j]+1, A[i,j-1]+1)

endfor

endfor

return A[m,n]

Question 17 |

Consider the function M defined as follows:
(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.)

Explanation |

Question 17 Explanation:

(a) M (101) = M (99) = M (87) = 91

(b) The following is a simple algorithm for computing M . It just compares n with 100, and either subtracts 10 from n or returns a constant, all of which are constant- time operations.

if (n> 100) return (n-10) else return 91

To prove that the algorithm is correct, we need to show that M (n) = 91 for n < 101. Notice first that M (101) = 91. From the following claim, it follows that M (n) = 91 for all n ≤ 100

Claim: For all k ≥ 1 and all n such that 101 − 11k ≤ n < 101 − 11(k − 1), M (n) = 91.

The proof of the claim is by induction on k.

Suppose k = 1 and 90 ≤ n < 101.

M (n)

= M (M (n + 11))

= M (n + 11 − 10) ( since n + 11 ≥ 101)

= M (n + 1)

Therefore, M (90) = M (91) = · · · = M (100) = M (101) = 91.

Assume the claim holds for k ≤ m. Consider n such that 101 − 11k ≤ n < 101 − 11(k − 1) for k = m + 1.

M (n) = M (M (n + 11))

= M (91) (M (n + 11) = 91, by IH )

= 91 by base case

Thus the claim holds for all k, and hence M (n) = 91 for all n < 101.

(b) The following is a simple algorithm for computing M . It just compares n with 100, and either subtracts 10 from n or returns a constant, all of which are constant- time operations.

if (n> 100) return (n-10) else return 91

To prove that the algorithm is correct, we need to show that M (n) = 91 for n < 101. Notice first that M (101) = 91. From the following claim, it follows that M (n) = 91 for all n ≤ 100

Claim: For all k ≥ 1 and all n such that 101 − 11k ≤ n < 101 − 11(k − 1), M (n) = 91.

The proof of the claim is by induction on k.

Suppose k = 1 and 90 ≤ n < 101.

M (n)

= M (M (n + 11))

= M (n + 11 − 10) ( since n + 11 ≥ 101)

= M (n + 1)

Therefore, M (90) = M (91) = · · · = M (100) = M (101) = 91.

Assume the claim holds for k ≤ m. Consider n such that 101 − 11k ≤ n < 101 − 11(k − 1) for k = m + 1.

M (n) = M (M (n + 11))

= M (91) (M (n + 11) = 91, by IH )

= 91 by base case

Thus the claim holds for all k, and hence M (n) = 91 for all n < 101.

There are 17 questions to complete.