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

Question 1
The regular expression (a ∗ + b) ∗ is equivalent to which of the following regular expressions:
A
a ∗ b ∗
B
(a ∗ b + b) ∗
C
(a + b ∗ ) ∗
D
(a ∗ b) ∗
       Theory-of-Computation       Regular-Expression
Question 1 Explanation: 
(a ∗ + b) ∗ allows any string over {a, b} and is the same as (a + b) ∗ . Option (a) only allows strings of the form a i b j . Options (b) and (d) do not allow strings of the form a i with no b’s.
Question 2
An FM radio channel has a repository of 10 songs. Each day, the channel plays 3 distinct songs that are chosen randomly from the repository. Mary decides to tune in to the radio channel on the weekend after her exams. What is the probability that no song gets repeated during these 2 days?
A
B
C
D
       Engineering-Mathematics       Probability
Question 2 Explanation: 
Question 3
Four siblings go shopping with their father. If Abhay gets shoes, then Asha does not get a necklace. If Arun gets a T-shirt, then Aditi gets bangles. If Abhay does not get shoes or Aditi gets bangles, the mother will be happy. Which of the following is true?
A
If the mother is happy, then Aditi got bangles.
B
If Aditi got bangles, then Abhay got shoes.
C
If the mother is not happy, then Asha did not get a necklace and Arun did not get a T-shirt.
D
None of the above.
       Engineering-Mathematics       Propositional-Logic
Question 3 Explanation: 
Let p denote that Asha get a necklace, q denote that Abhay gets shoes, r denote that Arun gets a T-shirt, s denote that Aditi gets bangles and w denote that mother is happy. The question is equivalent to the formula φ : q → ¬p ∧ r → s ∧ (¬q ∨ s) → w. A formula ψ is a valid implication iff every truth assignment to p, q, r, s, w that makes φ true also makes ψ true. Option (a) is the formula ψ a : w → s, option (b) is the formula ψ b : s → q and option (c) is the formula ψ c : ¬w → (¬p ∧ ¬r). Neither ψ a nor ψ b are valid implications but ψ c is.
Question 4
City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at intersections with traffic lights so that any segment of road can be reached by at least one ambulance that does not have to pass through a traffic light to reach the scene of the accident. If we model the road network as a graph, where intersections with traffic lights are vertices and edges represent road segments between traffic lights, the graph theoretic question to be answered is:
A
Find a spanning tree with minimum number of edges.
B
Find a spanning tree with minimum cost.
C
Find a minimal colouring.
D
Find a minimum size vertex cover.
       Engineering-Mathematics       Graph-Theory
Question 4 Explanation: 
Each ambulance “covers” the adjacent roads, and all roads are covered in this way.
Question 5
Let G be an arbitrary graph on n vertices with 4n − 16 edges. Consider the following statements: I There is a vertex of degree smaller than 8 in G. II There is a vertex such that there are less than 16 vertices at distance exactly 2 from it. Which of the following is true:
A
I only
B
II only
C
Both I and II
D
Neither I nor II
       Engineering-Mathematics       Graph-Theory
Question 5 Explanation: 
By the Pigeonhole Principle, there is a vertex of degree < 8.
As a counterexample to II, take, for instance a cycle on n − k vertices u 1 , . . . , u n−k (k to be fixed). Take a vertex v 0 and connect it to all the n − k cycle vertices to obtain a wheel with n − k + 1 vertices. Now take k − 1 vertices v 1 , . . . , v k−1 . For each i in [1, . . . , k − 1] connect v i to k + 3 equally spaced vertices C v i on the cycle so that C v i is connected to u i , u i+b((n−k)/(k+3)c , .
Thus there are (n − k) + 1 + (k − p 1) = n vertices and (n − k) + (n − k) + (k − 1)(k + 3) = 2n − 3 + k 2 = 4n − 16 for k =roof of (2n − 13)
Each u i is at distance exactly 2 from each of its non-neighbours on the cycle (via v 0 ) for (n − k − 3) = Ω(n) vertices at distance 2. Each v j is at distance exactly 2 from at least all the other v k vertices (plus at least 2ku i vertices if j not equal to 0) for at least k − 1 = Ω(sqrt(n)) vertices at distance 2.
Question 6
What does the following function compute in terms of n and d, for integer values of d? Note that the operation / denotes floating point division, even if the arguments are both integers. function foo(n,d){ if (d == 0){ return 1; }else{ if (d < 0){ return foo(n,d+1)/n; }else{ return n*foo(n,d-1); }}}
A
log d n if d < 0, n d if d > 0.
B
n d for all values of d.
C
n × d if d > 0, n ÷ d if d < 0.
D
n × d for all values of d.
       Programming       Functions
Question 6 Explanation: 
For d > 0, this computes n d by repeated multiplication. For d negative, the answer is 1/nd by repeated division.
Question 7
Consider the following functions f() and g(). f(){ w = 5; w = 2*z + 2; } g(){ z = w+1; z = 3*z - w; print(z); } We start with w and z set to 0 and execute f() and g() in parallel—that is, at each step we either execute one statement from f() or one statement from g(). Which of the following is not a possible value printed by g()?
A
-2
B
-1
C
2
D
4
       Programming       Functions
Question 7 Explanation: 
The possible values are : {-1,-2,3,4,7,13}, corresponding to the interleavings below.
Question 8
A stable sort preserves the order of values that are equal with respect to the comparison function. We have a list of three dimensional points [(7, 1, 8), (3, 5, 7), (6, 1, 4), (6, 5, 9), (0, 2, 5), (9, 0, 9)]. We sort these in ascending order by the second coordinate. Which of the folllowing corresponds to a stable sort of this input?
A
[(9, 0, 9), (7, 1, 8), (6, 1, 4), (0, 2, 5), (6, 5, 9), (3, 5, 7)]
B
[(0, 2, 5), (3, 5, 7), (6, 1, 4), (6, 5, 9), (7, 1, 8), (9, 0, 9)]
C
[(9, 0, 9), (7, 1, 8), (6, 1, 4), (0, 2, 5), (3, 5, 7), (6, 5, 9)]
D
[(9, 0, 9), (6, 1, 4), (7, 1, 8), (0, 2, 5), (3, 5, 7), (6, 5, 9)]
       Algorithms       Sorting
Question 8 Explanation: 
In a stable sort, the original order of the pairs (7,1,8),(6,1,4) and (3,5,7),(6,5,7) with equal second coordinates must be preserved in the sorted output.
Question 9
Suppose we constructed the binary search tree shown at the right by starting with an empty tree and inserting one element at a time from an input sequence, without any rotations or other manipulations. Which of the following assertions about the order of elements in the input sequence cannot be true?
A
8 came after 3 and 19 came after 29.
B
7 came before 8 and 23 came after 37.
C
1 came after 12 and 29 came before 42.
D
3 came before 14 and 16 came before 28.
       Data-Structures       Binary-search-tree
Question 9 Explanation: 
28 is an ancestor of 16, so 16 must have come after 28. In the tree only ancestor-descendant relationships matter in determining the order in which elements arrive.An ancestor must always come before any of its descendants. Incomparable elements could come in any order.
Question 10
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is a valid inference?
A
If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A
B
If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
C
If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for B.
D
If we don’t know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A.
       Algorithms       P-NP
Question 10 Explanation: 
If we have a polynomial time solution for B, the reduction gives us a polynomial time solution for A.
Question 11
Let Σ = {a, b, c}. Let L even be the set of all even length strings in Σ ∗ . (a) Construct a deterministic finite state automaton for L even . (b) We consider an operation Erase ab that takes as input a string w ∈ Σ ∗ and erases all occurrences of the pattern ab from w. Formally, it can be defined as follows:
A
Descriptive Explanation
       Theory-of-Computation       Finite-Automata
Question 11 Explanation: 
(a) L even can be recognized by an automaton with two states {q 0 , q 1 }, where q 0 is both an initial and final state. On input letters a and b, the automaton switches from q 0 and q 1 and vice versa. An odd length input will take the automaton to q 1 and an even length input will take the automaton to q 0 .
Question 12
There are a number of tourist spots in a city and a company GoMad runs shuttle services between them. Each shuttle plies between a designated origin and destination, and has a name. Due to lack of coordination, the same name may be allotted to multiple routes. To make matters worse, another company GoCrazy introduces its shuttle services using the same set of shuttle names. A GoMad shuttle and a GoCrazy shuttle with the same name may start at different origins and/or end at different destinations. A pass from a company allows unlimited travel in all the company’s shuttles. For each company, we have a list that specifies all routes allotted to each shuttle name. Design an algorithm to find out if there is a source s, a target t, and a sequence of shuttle names σ such that, irrespective of whether you are carrying a GoMad pass or a GoCrazy pass, you can start at s and arrive at t using the sequence σ.
A
Descriptive Explanation
       Algorithms
Question 12 Explanation: 
Create a graph where the set of vertices are pairs (Spot 1, Spot 2) of tourist spots. There is an edge labeled “Name 1” from (Spot 1, Spot 2) to (Spot 3, Spot 4) iff there is a GoMad shuttle “Name 1” from Spot 1 to Spot 3 and a GoCrazy shuttle “Name 1” from Spot 2 to Spot 4. The answer to the question is yes iff there is a directed path from a vertex (Spot 1, Spot 1) to a vertex (Spot 2, Spot 2).
Question 13
Let Σ = {a, b}. Given words u, v ∈ Σ ∗ , we say that v extends u if v is of the form xuy for some x, y ∈ Σ ∗ . Given a fixed word u, we are interested in identifying whether a finite state automaton accepts some word that extends u. Describe an algorithm that takes as input a finite state automaton (DFA or NFA) A over Σ = {a, b} and a word u ∈ Σ ∗ and reports “Yes” if some word in the language of A extends u and “No” if no word in the language of A extends u.
A
Descriptive Explanation
       Theory-of-Computation       Finite-Automata
Question 13 Explanation: 
Let R be the set of states that can be reached by a path from the initial state in A and let S be the set of states from which there is a path to one of the final states in A.
For each pair of states (r, s) ∈ R × S, A r,s is obtained from A by keeping the set of states and set of transitions unchanged, but making r the unique intial state and s the unique final state.
If u ∈ L(A r,s ), then there must be a word xuy ∈ L(A), where x labels the path from the initial state to r (r ∈ R is reachable from the initial state), u labels the path from r to s, and y labels the path from s to some final state of A (s ∈ S, so such a path must exist.)
Hence, output “Yes” if u ∈ L(A r,s ) for some (r, s) ∈ R × S, and “No” otherwise.
Question 14
In a party there are 2n participants, where n is a positive integer. Some participants shake hands with other participants. It is known that there are no three participants who have shaken hands with each other. Prove that the total number of handshakes is not more than n 2 .
A
Descriptive Explanation
       Engineering-Mathematics       Combinatorics
Question 14 Explanation: 
Model this as a graph problem, we are looking for a graph without a triangle. We show that the maximum number of edges that a triangle-free graph on 2n vertices can have is n 2 .
The proof by induction on n.
The base cases n = 1, 2 are easy to see by inspection.
For the inductive step, let n ≥ 3. If the graph G has no edges then there is nothing to prove. Otherwise, take an edge {x, y}, and consider the graph G' on 2(n − 1) vertices obtained by deleting both the vertices {x, y} from G.
By the inductive hypothesis, G' has at most (n − 1) 2 edges. Since graph G is triangle- free and {x, y} is an edge in G, there is no vertex v in G' such that both {v, x} and {v, y} are edges in G. So the number of edges with one end-point in the set {x, y} and the other in the set of vertices of G 0 is at most the number of vertices in G' , namely 2(n − 1).
Now the set of edges of G consists of (i) all the edges in G' , plus (ii) the one edge {x, y}, plus (iii) the at most 2(n − 1) edges with exactly one end-point in {x, y}. So the number of edges of G is at most (n − 1) 2 + 1 + 2(n − 1) ≤ n 2 .
Question 15
An undirected graph is connected if, for any two vertices {u, v} of the graph, there is a path in the graph starting at u and ending at v. A tree is a connected, undirected graph that contains no cycle. (a) A leaf in a tree is a vertex that has degree 1. Prove that if G is a tree with at least two vertices then G contains at least two leaves. (b) A bipartite graph is one in which the vertex set V can be partitioned into two disjoint sets V 1 and V 2 so that for every edge {u, v}, u and v lie in different partitions—that is, u ∈ V 1 and v ∈ V 2 or vice versa. Prove that if G is a tree with at least two vertices, then G is bipartite.
A
Descriptive Explanation
       Engineering-Mathematics       Graph-Theory
Question 15 Explanation: 
(a) Consider a maximal path ρ = v 0 v 1 . . . v k in the tree. If v0 is not a leaf, then it has a neighbour v not equal to v 1 , and the path ρ can be extended to a longer one vρ since there are no cycles. This contradicts the fact that ρ is maximal, thereby showing that v 0 is a leaf. A similar argument shows that v k is also a leaf.
(b) If we root the tree at any node, we can colour the tree level by level by alternating two colours. This 2-colouring gives us the partition of the vertex set
Question 16
A
Descriptive Explanation
       Algorithms       Time-Complexity
Question 16 Explanation: 
Compute two arrays A and B with A[i] and B[i] giving the length of the longest such sequence in (a 1 , b 1 ), . . . (a i , b i ) with a i and b i as the last elements, respectively.
Note that A[1] = 1 and B[1] = 1. To compute A[i] and B[i] for i ≥ 2, we first compute the following quantities:
Question 17
Consider the following function that takes as input a sequence A of integers with n elements, A[1], A[2], . . . , A[n] and an integer k and returns an integer value. The function length(S) returns the length of sequence S. Comments start with //. function mystery(A, k){ n = length(A); if (k > n) return A[n]; v = A[1]; AL = [ A[j] : 1 <= j <= n, A[j] < v ]; // AL has elements < v in A Av = [ A[j] : 1 <= j <= n, A[j] == v ]; // Av has elements = v in A AR = [ A[j] : 1 <= j <= n, A[j] > v ]; // AR has elements > v in A if (length(AL) >= k) return mystery(AL,k); if (length(AL) + length(Av) >= k) return v; return mystery(AR, k - (length(AL) + length(Av))); } (a) Explain what the function computes. (b) What is the worst-case complexity of this algorithm in terms of the length of the input sequence A? (c) Give an example of a worst-case input for this algorithm.
A
Descriptive Explanation
       Programming       Functions
Question 17 Explanation: 
(a) mystery(A, k) finds the kth element in A in ascending order. This is a divide-and- conquer selection algorithm, similar to quicksort.
(b) The worst case complexity is O(n 2 ) because of the fixed choice of pivot, as in quicksort.
(c) A typical worst case input would be, for instance, where A is in ascending order and k = n.
There are 17 questions to complete.