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

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?
A
Only (i) is true.
B
Only (ii) is true.
C
Both (i) and (ii) are true.
D
Neither (i) nor (ii) is true.
       Data-Structures       Graphs-and-Tree
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?
A
Only (i) is true.
B
Only (ii) is true.
C
Both (i) and (ii) are true.
D
Neither (i) nor (ii) is true.
       Engineering-Mathematics       Propositional-Logic
Question 2 Explanation: 
(i) is false. Note that (a 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?
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.
       Theory-of-Computation       Regular-Expression
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?
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).
       Data-Structures       Graphs-and-Tree
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?
A
60 edges and 20 vertices.
B
30 edges and 20 vertices.
C
60 edges and 50 vertices.
D
30 edges and 50 vertices.
       Engineering-Mathematics       Graph-Theory
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; } }
A
k == i-j.
B
k == j-i.
C
k == -j-i.
D
Depends on start and end.
       Programming       Functions
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 ?
A
1/5
B
1/3
C
2/5
D
1/2
       Engineering-Mathematics       Probability
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?
A
Playing tennis.
B
Watching tennis.
C
Reading about tennis.
D
None of the above.
       Engineering-Mathematics       Propositional-Logic
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?
A
34
B
32
C
17
D
16
       Engineering-Mathematics       Graph-Theory
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)?
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.
       Programming       Scope-of-variable
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.)
A
Explanation
       Algorithms
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.
A
Explanation
       Engineering-Mathematics       Graph-Theory
Question 12 Explanation: 
Build a path in the graph as follows:
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.
A
Explanation
       Engineering-Mathematics       Graph-Theory
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.
A
Explanation
       Engineering-Mathematics       Set-Theory
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.
A
Explanation
       Theory-of-Computation       DFA
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 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)?
A
Explanation
       Algorithms       Dynamic-Programming
Question 16 Explanation: 
Let x = a 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 that

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]
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.)
A
Explanation
       Programming       Functions
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.
There are 17 questions to complete.