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?
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)?
Question 4 Explanation: 
Note that d(u) ⩽ d(v) + 1
Question 5
How many paths are there in the plane from (0, 0) to (m, n) ∈ N × N, if the possible steps from (i, j) are either (i + 1, j) or (i, j + 1)?
m n
Question 5 Explanation: 
From a vertex (i, j) with either i > m or j > n, it is not possible to reach (m, n). Therefore one cannot overshoot m on the x-axis, and n on the y-axis. The total number of steps required to reach (m, n) is m + n (m steps on the x-axis and n on the y-axis). Among the m + n steps, the m x-axis steps and n y-axis steps can be distributed in any manner. This is obtained by choosing n steps for the y-axis (the rest would go to the x-axis).
Question 6
You are given two coins A and B that look identical. The probability that coin A turns up heads is 1/4 , while the probability that coin B turns up heads is 3/4 . You choose one of the coins at random and toss it twice. If both the outcomes are heads, what is the probability that you chose coin B?
Question 6 Explanation: 
Pr[2 heads | B is chosen ] = 9/16 and Pr[2 heads | A is chosen ] = 1/16. Hence
Pr[B is chosen | 2 heads ] = 0.9.
Question 7
Let C n be the number of strings w consisting of n X’s and n Y ’s such that no initial segment of w has more Y ’s than X’s. Now consider the following problem. A person stands on the edge of a swimming pool holding a bag of n red and n blue balls. He draws a ball out one at a time and discards it. If he draws a blue ball, he takes one step back, if he draws a red ball, he moves one step forward. What is the probability that the person remains dry?
C n /2 2n
n . Cn / (2n)!
Question 7 Explanation: 
The total number of ways of choosing 2n balls where n balls are ( identical of one type, and the other n balls are identical of a different type is (2n)! / (n! . n!) = For the person to remain dry, at any point of time he should have chosen more red balls than blue balls. This is given by C n . Hence the answer is (b).
Question 8
There are 7 switches on a switchboard, some of which are on and some of which are off. In one move, you pick any 2 switches and toggle each of them—if the switch you pick is currently off, you turn it on, if it is on, you turn it off. Your aim is to execute a sequence of moves and turn all 7 switches on. For which of the following initial configurations is this not possible? Each configuration lists the initial positions of the 7 switches in sequence, from switch 1 to switch 7.
Question 8 Explanation: 
The parity of switches in each position is unchanged after each move. If all 7 switches are on at the end, the final parity of ”off” is even and of ”on” is odd. So we can only achieve this if we start with a configuration where the number of ”off” switches is even and the number of ”on” switches is odd. The exact order does not matter since we can pick any two to toggle at each step.
Question 9
Your college has sent a contingent to take part in a cultural festival at a neighbouring institution. Several team events are part of the programme. Each event takes place through the day with many elimination rounds. Your contingent is multi-talented and each individual has the skills to take part in a subset of the events. However, the same individual cannot be part of the team for two different events because of a possible clash in timings. Your aim is to create teams to take part in as many events as possible.
To do this, you decide to model the problem as a graph where the nodes are the events and edges represent pairs of events where the team that you plan to send shares a member. In this setting, the graph theoretic question to be answered is:
Find a maximum length simple cycle
Find a maximum size independent set
Find a maximum matching
Find a maximal connected component
Question 10
What does the following function compute in terms of n and d, for integer values of n and d, d > 1? Note that a//b denotes the quotient (integer part) of a ÷ b, for integers a and b. For instance 7//3 is 2.
function foo(n,d){
x := 0;
while (n >= 1) {
x := x+1;
n := n//d;
The number of ways of choosing d elements from a set of size n.
The number of ways of rearranging d elements from a set of size n.
The number of digits in the base d representation of n.
The number of ways of partitioning n elements into groups of size d.
Question 10 Explanation: 
The code computes ⌊log d (n)⌋ + 1.
Question 11
Consider the following non-deterministic finite automata (NFA) A 1 and A 2 :

(a) Give an example of a word which is accepted by both A 1 and A 2.
(b) Give an example of a word which is accepted by A 1 , but not by A 2 .
(c) Draw the deterministic finite automaton (DFA) equivalent to A 1 .
Descriptive Explanation
Question 11 Explanation: 
(a) ba
(b) a
(c) The equivalent DFA is given in figure.
Question 12
A student requests a recommendation letter from a professor. The professor gives three sealed envelopes. Each envelope contains either a good recommendation letter or a bad recommendation letter.
(a) Make a list of all the possible scenarios.
(b) Suppose now the professor tells the student that exactly one envelope contains a good recommendation letter and the other two contain bad recommendation letters. In the list of scenarios you prepared above, mark the ones that are still possible.
(c) On envelope 1 is written the clue “This contains a bad recommendation letter”. On envelope 2 is written the clue “This contains a bad recommendation letter”. On envelope 3 is written the clue “Envelope 2 contains a good recommendation letter”. Suppose now the professor gives the additional information that exactly one of these three clues are true and the other two are false. Can the student find out the contents of the envelopes without breaking their seals?
Descriptive Explanation
Question 12 Explanation: 
(a) For i ∈ {1, 2, 3}, let g i denote that letter i is good, and b i denote that it is bad. Here are the possible scenarios:

(b) 2, 3 and 5.
(c) The professor says that exactly one of the three clues is true, and from part (b), we see that exactly one letter is good. Let clue i denote the clue on envelope i. Now it cannot be the case that both clue 1 and clue 2 are false, since then both envelope 1 and envelope 2 would contain good letters, contradicting part (b). Therefore one of clue 1 and clue 2 is true, and clue 3 is definitely false. Since clue 2 and clue 3 assert opposite facts, this means that clue 2 is true (and hence clue 1 is false). Thus we have that both g 1 and b 2 hold. Since exactly one letter is good, it follows that b 3 holds. Hence the exact scenario is g 1 b 2 b 3 .
Question 13
Let G be a simple graph on n vertices.
(a) Prove that if G has more than edges then G is connected.
(b) For every n > 2, find a graph G n which has exactly n vertices and edges,and is not connected.
Descriptive Explanation
Question 13 Explanation: 
Question 14
You are given a sorted array of n elements which has been circularly shifted. For example, {35, 42, 5, 12, 23, 26} is a sorted array that has been circularly shifted by 2 positions.
Give an O(log n) time algorithm to find the largest element in a circularly shifted array. (The number of positions through which it has been shifted is unknown to you.)
Descriptive Explanation
Question 14 Explanation: 
Let n be the number of elements in the array. If the array is not shifted at all, then the first element is smaller than the last element. Say the array is shifted by m positions, for m > 0. If m < n/2 , then the first element would be larger than the middle element (and the largest element lies in the first half). If m >= n/2 then the last element would be smaller than the middle element (and the largest element lies in the second half). This suggests a recursive algorithm which reduces the search space by half at each call, and hence gives a running time of O(log n).
The following code describes this algorithm: a/b gives the integer part of dividing a by b. The required solution is obtained by calling f(T, 0, n-1), where n is the length of T.
function f(T, first, last)
if (T[first] <= T[last])
return T[last]
else {
mid := first + (last - first)/2
if (T[mid] > T[mid+1])
return T[mid]
else if (T[first] > T[mid])
return f(T, first, mid-1)
else if (T[mid] >= T[last])
return f(T, mid+1, last)
Question 15
Let G = (V, E) be an undirected graph and V = {1, 2, . . . , n}. The input graph is given to you by a 0-1 matrix A of size n × n as follows. For any 1 ≤ i, j ≤ n, the entry A[i, j] = 1 if and only if (i, j) is an edge in G.
A connected component in G is a subgraph in which any two vertices are connected to each other by paths. Give a simple algorithm to find the number of connected components in G. Analyze the time taken by your procedure.
Descriptive Explanation
Question 15 Explanation: 
We assume that there is a separate boolean array of size n that tells which vertex is marked. Initially all vertices are unmarked. Start at vertex 1 and perform a BFS (breadth-first search). The set of vertices marked during this procedure constitute the connected component that 1 belongs to. The time taken is O(n × size of this connected component). Now perform a linear search for the first unmarked vertex, and start a BFS with that as starting point. Once the BFS terminates, we search for the next unmarked vertex. We repeat this procedure till all vertices are marked. The number of times we start a BFS with a new vertex in the above procedure is the number of connected components.
Each BFS takes time O(n × size of that connected component). Since the connected components partition V , and since we never run a BFS on each connected component more than once, the overall time taken by all the breadth-first searches is O(n 2 ). Since we search for a new unmarked vertex (to start a new BFS) at most nn times, and since each search takes at most n time, the overall time taken by the above procedure is still O(n 2 ).
Question 16
You are playing an old-style video game in which you have to shoot down alien space- ships as they fly across the screen from left to right. Each spaceship flies across the screen at a specified height. You have an antiaircraft gun set to shoot down all space- ships at a certain height. Spaceships fly one at a time, so if your gun is set to fire at the correct height, it will shoot down the spaceship currently flying across the screen.
You can set the initial height at which the gun fires. As the game progresses, you can reset the height, but only to a lower value. You are given in advance the height at which each spaceship flies. There are N spaceships numbered 1, 2, . . . , N in the order in which they fly across the screen. For 1 ≤ i ≤ N , h[i] denotes the height at which spaceship i flies.
(a) Let V [i] denote the maximum number of spaceships from i, i+1, . . . , N that you can shoot down with a single gun. Write a recurrence for V [i] and describe a strategy to compute V [i] using dynamic programming. What is the space and time complexity of your solution?
(b) Describe an algorithm to compute the minimum number of guns required to shoot down all the spaceships. Each gun can be initialized separately to a firing height and each gun can be separately reset to a lower value.
Descriptive Explanation
Question 16 Explanation: 
(a) If we view h[1], . . . , h[N ] as a list of numbers, we are essentially asked to find the length of the longest descending subsequence. The recurrence is as follows:
V [N ] = 1
V [i] = 1 + max{V [j] | j > i and h[i] ⩾ h[j]}
The dynamic programming algorithm maintains an array V of size N , to be filled in from V [N ] to V [1]. Computing the value of V [i] takes O(N ) time, since it involves potentially examining all entries from V [i + 1] to V [N ]. Thus the time taken overall is O(N 2 ). The space required is O(N ).
(b) The above algorithm can be modified to produce not just the length of the longest descending subsequence, but the subsequence itself. Once we do this, we delete these entries from the h list and find the longest descending subsequence now. We repeat this process till the original h list has been decomposed into disjoint descending subsequences. Since each of these subsequences can be handled by one gun, the minimum number of guns required to shoot down all the spaceships is the number of disjoint subsequences computed above.
Question 17
A First In First Out queue is a data structure supporting the operations Enque, Deque, Print. Enque(x) adds the item x to the tail of the queue. Deque removes the element at the head of the queue and returns its value. Print prints the head of the queue.
(a) You are given a queue containing 5 elements. Using a single additional temporary variable X, write down a sequence of statements each being one of Enque, Deque, Print so that the output of the program results in the 5 elements of the queue being printed in reverse order.
(b) If the queue had n elements to begin with, how many statements would you need to print the queue in reverse order?
Descriptive Explanation
Question 17 Explanation: 
(a) Assume the queue contains 1,2,3,4,5 in order, with 1 at the head. We display below the sequence of instructions and the state of the queue whenever it changes.

(b) Each time we do an X = Deque followed by an Enque(X), we move the element at the head to the tail. Repeating these two statements n − 1 times moves the last element to the head, while preserving the order among the rest of the list. Issuing a Print instruction now prints the current head of the list (which was originally the last element).
Thus we need 2(n − 1) + 1 instructions to move the last element to the head and print it. At this point, the last element is what was originally the last but one element. If we now repeat the above block of 2(n − 1) + 1 instructions, we print the second last element of the original queue, while bringing the last two elements of the original queue to the head.
Extending this logic, we see that if repeat the block of code n times, we end up printing the queue in reverse. The number of statements required is n(2n − 1).
There are 17 questions to complete.