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?
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 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).
(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.
There are 4 questions to complete.