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

aba | |

bab | |

abba | |

aabb |

Question 1 Explanation:

Word should start with an a and end with b, or start with b and end with a.

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?

Chetan does not attend | |

Akash does not attend | |

either (a) or (b) | |

none of the above |

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?

Geetha finishes ahead of Divya and Vani finishes ahead of Shalini. | |

Aparna finishes ahead of Shalini. | |

Divya finishes ahead of Geetha. | |

None of the above. |

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

2 | |

-1 | |

0 | |

1 |

Question 4 Explanation:

Note that d(u) ⩽ d(v) + 1