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

 Question 1
Which of the words below matches the regular expression a(a + b)* b + b(a + b)* a?
 A aba B bab C abba D aabb
Theory-of-Computation       Regular-Expression
Question 1 Explanation:
 Question 2
Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan attend, then Deepa will attend too. If Bharani does not attend, then Akash will not attend. If Deepa does not attend, which of the following is true?
 A Chetan does not attend B Akash does not attend C either (a) or (b) D none of the above
Engineering-Mathematics       Propositional-Logic
Question 2 Explanation:
If Deepa does not attend, then one of Chetan and Bharani is absent. The first case is (a). The second case is that Bharani does not attend – but it is given that Akash will not attend if Bharani does not attend. So in the second case, (b) holds. So either (a) holds or (b) holds, and hence the correct answer is (c).
 Question 3
In a running race, Geetha finishes ahead of Shalini and Vani finishes after Aparna. Divya finishes ahead of Aparna. Which of the following is a minimal set of additional information that can determine the winner?
 A Geetha finishes ahead of Divya and Vani finishes ahead of Shalini. B Aparna finishes ahead of Shalini. C Divya finishes ahead of Geetha. D None of the above.
Aptitude       Reasoning
Question 3 Explanation:
Given: Geetha > Shalini and Divya > Aparna > Vani. The minimal extra information needed to decide the winner is a comparison between Geetha and Divya. (a) is not correct since it gives additional comparison between Vani and Shalini. (b) is not correct since it does not decide the winner. (c) is the correct option, since it decides Divya to be the winner and does not provide any extra information. (d) is not a correct option because option (c) is correct.
 Question 4
Let G = (V, E) be an undirected simple graph, and s be a designated vertex in G. For each v ∈ V , let d(v) be the length of a shortest path between s and v. For an edge (u, v) in G, what can not be the value of d(u) − d(v)?
 A 2 B -1 C 0 D 1
Engineering-Mathematics       Graph-Theory
Question 4 Explanation:
Note that d(u) ⩽ d(v) + 1
There are 4 questions to complete.

Register Now