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

Please wait while the activity loads.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

Question 1 |

Twin primes are pairs of numbers p and p+2 such that both are primes—for instance, 5 and 7, 11 and 13, 41 and 43. The Twin Prime Conjecture says that there are infinitely many twin primes.
Let TwinPrime(n) be a predicate that is true if n and n+2 are twin primes. Which of the following formulas, interpreted over positive integers, expresses that there are only finitely many twin primes?

∀m. ∃n. m ≤ n and not(TwinPrime(n)) | |

∃m. ∀n. n ≤ m implies TwinPrime(n) | |

∀m. ∃n. n ≤ m and TwinPrime(n) | |

∃m. ∀n. TwinPrime(n) implies n ≤ m |

Question 1 Explanation:

This says that there is a bound, m, such that any twin prime is below m. In other words, that there only finitely many twin primes.

Question 2 |

A binary relation R ⊆ (S × S) is said to be Euclidean if for every a, b, c ∈ S, (a, b) ∈ R and (a, c) ∈ R implies (b, c) ∈ R. Which of the following statements is valid?

If R is Euclidean, (b, a) ∈ R and (c, a) ∈ R, then (b, c) ∈ R, for every a, b, c ∈ S. | |

If R is reflexive and Euclidean, (a, b) ∈ R implies (b, a) ∈ R, for every a, b ∈ S. | |

If R is Euclidean, (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for every a, b, c ∈ S. | |

None of the above. |

Question 2 Explanation:

(a) This option is not valid. Consider the set S = {d, e, a, b, c} and the relation R given below.

R = {(d, a), (e, a), (a, a), (a, b), (a, c), (b, b), (c, c), (b, c), (c, b)}

R is Euclidean but (a) is violated by {d, e, a}.

(b) This option is valid. Suppose R is reflexive. Then (a, a) ∈ R for every a. If (a, b) ∈ R, then by the definition of Euclidian, (b, a) ∈ R.

(c) This option is not valid. Consider the set S = {a, b, c} and the relation R given below.

R = {(a, b), (b, b), (b, c), (c, c)}

R is Euclidean but not transitive, since (a, c) 6∈ R.

(d) Since (b) is valid, this cannot be the correct answer.

R = {(d, a), (e, a), (a, a), (a, b), (a, c), (b, b), (c, c), (b, c), (c, b)}

R is Euclidean but (a) is violated by {d, e, a}.

(b) This option is valid. Suppose R is reflexive. Then (a, a) ∈ R for every a. If (a, b) ∈ R, then by the definition of Euclidian, (b, a) ∈ R.

(c) This option is not valid. Consider the set S = {a, b, c} and the relation R given below.

R = {(a, b), (b, b), (b, c), (c, c)}

R is Euclidean but not transitive, since (a, c) 6∈ R.

(d) Since (b) is valid, this cannot be the correct answer.

Question 3 |

Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured
edge or not an endpoint of any green coloured edge. If a graph G does not satisfy this property, which of the following statements about G are valid?

There is a red coloured edge. | |

Any vertex that is the endpoint of a red coloured edge is also the endpoint of a green coloured edge. | |

There is a vertex that is not an endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge. | |

(a) and (c). |

Question 3 Explanation:

Let r(x) denote the fact that the vertex x is the endpoint of a red coloured edge, and similarly for b(x) and g(x). The given property P can be expressed by the following formula.

∀x. [r(x) =⇒ b(x) ∨ ¬g(x)]

If a graph G does not satisfy the above property, then it means that there exists a vertex v satisfying

r(v) ∧ ¬b(v) ∧ g(v).

This is exactly what is stated in option (c).

Option (b) is not valid. Consider the graph G with vertex set V = {1, 2, 3} and (colored) edges given by

E = {((1, 2), red), ((1, 3), red), ((2, 3), green)}.

Vertex 3 witnesses the violation of the property P , but vertex 2 violates option (b).

Since (c) implies (a), (d) is the correct answer.

∀x. [r(x) =⇒ b(x) ∨ ¬g(x)]

If a graph G does not satisfy the above property, then it means that there exists a vertex v satisfying

r(v) ∧ ¬b(v) ∧ g(v).

This is exactly what is stated in option (c).

Option (b) is not valid. Consider the graph G with vertex set V = {1, 2, 3} and (colored) edges given by

E = {((1, 2), red), ((1, 3), red), ((2, 3), green)}.

Vertex 3 witnesses the violation of the property P , but vertex 2 violates option (b).

Since (c) implies (a), (d) is the correct answer.

Question 4 |

A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable. The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:

Find a spanning tree with minimum number of edges. | |

Find a minimal colouring. | |

Find a minimum size vertex cover. | |

Find a maximum size independent set. |

Question 4 Explanation:

If we represent each slot by a colour, then a colouring of the graph is an assignment of courses to slots, such that courses with overlapping audiences are in different slots. A minimal colouring minimizes the number of slots needed.

Question 5 |

An undirected graph has 10 vertices labelled {1, 2, . . . , 10} and 37 edges. Vertices 1, 3, 5, 7, 9 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 10?

5 | |

6 | |

7 | |

8 |

Question 5 Explanation:

The sum of the degrees is twice the number of edges, which is 74 in this case. The degrees of the vertices {1, 2, . . . , 9} add up to 68. Hence 6 is the correct answer.

Question 6 |

Suppose we have constructed a polynomial time reduction from problem A to problem B. Which of the following can we infer from this fact?

If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A. | |

If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B. | |

If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for B. | |

If we don’t know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A. |

Question 6 Explanation:

If there were a polynomial time solution for B, we can use the reduction to obtain a polynomial time solution for A.

Question 7 |

You arrive at a snack bar and you can’t decide whether to order a lime juice or a lassi. You decide to throw a fair 6-sided die to make the choice, as follows.
• If you throw 2 or 6 you order a lime juice.
• If you throw a 4, you order a lassi.
• Otherwise, you throw the die again and follow the same algorithm.
What is the probability that you end up ordering a lime juice?

1/3 | |

1/2 | |

2/3 | |

3/4 |

Question 7 Explanation:

The probability of getting a lime juice on any throw is 1/3 . At any stage, the probability that you will throw the dice again is 1/2 . Hence the probability that you throw the dice
i times is 1/(2

^{i}−1).Thus the overall probability of getting a lime juice isQuestion 8 |

How many times is the comparison i ≥ n performed in the following program?
int i=85, n=5;
main() {
while (i >= n) {
i=i-1;
n=n+1;
}
}

40 | |

41 | |

42 | |

43 |

Question 8 Explanation:

The value of i − n is 80 initially. We run the loop as long as i − n ≥ 0 and in each iteration, i − n decreases by 2. Just before the k th time the comparison is performed (for k ≥ 1), the value of i−n is 80−2k+2. Hence just before the forty-first comparison, the value of i − n is 0. After the forty-first comparison, the loop is executed one last time. We need to make the comparison once more to exit the loop. Thus the correct answer is 42.

Question 9 |

Let L

_{1}and L_{ 2}be languages over an alphabet Σ such that L_{ 1}⊆ L_{ 2}. Which of the following is true:If L _{2} is regular, then L_{ 1} must also be regular. | |

If L _{1} is regular, then L_{ 2} must also be regular. | |

Either both L _{1} and L_{ 2} are regular, or both are not regular. | |

None of the above. |

Question 9 Explanation:

Let A = {w ∈ {a, b} ∗ | w has equal number of as and bs}. It is well known that B is not regular. It is also known that ∅ and {a, b} ∗ are regular.

Now, taking L

Now, taking L

_{ 1}= A and L_{ 2}= {a, b} ∗ violates option (a). Taking L_{1}= ∅ and L_{ 2}= A violates option (b). Both the above examples violate option (c). Thus (d) is the correct answer.Question 10 |

The school athletics coach has to choose 4 students for the relay team. He calculates that there are 3876 ways of choosing the team if the order in which the runners are placed is not considered. How many ways are there of choosing the team if the order
of the runners is to be taken into account?

Between 12,000 and 25,000 | |

Between 30,000 and 60,000 | |

Between 75,000 and 99,999 | |

More than 100,000 |

Question 10 Explanation:

The actual answer is 3876 × 4! = 3876 × 24 = 93024.

Question 11 |

Let Σ = {a, b}. Given a language L ⊆ Σ ∗ and a word w ∈ Σ ∗ , define the languages:
Extend(L, w) := { xw | x ∈ L }
Shrink(L, w) := { x | xw ∈ L }
Show that if L is regular, both Extend(L, w) and Shrink(L,w) are regular.

Descriptive Explanation |

Question 11 Explanation:

If L is regular, there exists a regular expression r whose language equals L. The word w is a singleton language and can be represented by the regular expression w. Then, Extend(L, w) is the language given by the expression r.w. Hence Extend(L, w) is regular.

If L is regular, there is a deterministic finite automaton (DFA) A whose language is L. Mark all states q in this DFA such that reading w from q leads to an accepting state of A. Call this set of states F

If L is regular, there is a deterministic finite automaton (DFA) A whose language is L. Mark all states q in this DFA such that reading w from q leads to an accepting state of A. Call this set of states F

_{new}. The required DFA for Shrink(L, w) would have the same states, transitions and initial states as A. However, the set of accepting states would be F_{new}.Question 12 |

Consider a social network with n persons. Two persons A and B are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons F

_{1}, . . . , F_{ m}such that A and F_{1}are friends, F_{ 1}and F_{ 2}are friends, . . . , F_{ m−1}and F_{ m}are friends, and finally F_{ m}and B are friends. It is known that there are k persons such that no pair among them is connected. What is the maximum number of friendships possible?Descriptive Explanation |

Question 12 Explanation:

To solve the above question, consider an illustrative scenario where k is 2. Given that the graph has two connected components, what is the maximum number of edges possible.

To solve the above question, consider an illustrative scenario where k is 2. Given that the graph has two connected components, what is the maximum number of edges possible. Let the first connected component be G

Coming back to our original question: suppose the graph is made of k connected components, then the maximum number of edges is obtained when one of the components has n − (k − 1) vertices and the other components have 1 vertex each.

Hence the maximum number of edges possible is

To solve the above question, consider an illustrative scenario where k is 2. Given that the graph has two connected components, what is the maximum number of edges possible. Let the first connected component be G

_{ 1}with n_{ 1}vertices and the other be G_{2}with n_{ 2}vertices. Further assume that n_{1}≥ n_{ 2}. Note that there are no edges between a vertex from G_{1}and a vertex from G_{2}. Therefore, each vertex in G_{2}can be connected by an edge to at most n_{2}− 1 vertices. If a vertex from G_{ 2}is moved to G_{1}, then this vertex can potentially be part of n 1 edges. Since n_{ 1}≥ n_{ 2}, moving vertices from G_{ 2}to G_{ 1}would increase the number of edges. The maximum number of edges would be obtained when n 2 is 1 and n_{1}= n − 1.Coming back to our original question: suppose the graph is made of k connected components, then the maximum number of edges is obtained when one of the components has n − (k − 1) vertices and the other components have 1 vertex each.

Hence the maximum number of edges possible is

^{n−k+1}C_{2}.Question 13 |

A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down the hill. Once she goes down the steep hill, she can not climb back in time make more rotis.
(a) Suppose the cook starts at the top with R rupees. What are all the possible amounts of money she can have at the end?
(b) Suppose the cook can hitch a quick ride from her stall downhill back to the kitchen uphill, by offering a paan to a truck driver. If she starts at the top with P paans and 1 rupee, what is the minimum and maximum amount of money she can have at the end?

Descriptive Explanation |

Question 13 Explanation:

(a). R − M + 2S, where M ≤ R is the number of rotis made and S ≤ M is the number of rotis sold. The set of possible values is {0, 1, 2, . . . , 2R}.

(b) Minimum 0 rupees, by preparing 1 roti and doing nothing else. Maximum 2

(b) Minimum 0 rupees, by preparing 1 roti and doing nothing else. Maximum 2

_{P +1}rupees: she can first make one roti and sell it to get 2 rupees. She can then make P trips to the kitchen, doubling her money with every trip.Question 14 |

You are given n positive integers, d

_{1}≤ d_{ 2}≤ . . . ≤ d_{ n}, each greater than 0. Design a greedy algorithm to test whether these integers correspond to the degrees of some n-vertex simple undirected graph G = (V, E). (A simple graph has no self-loops and at most one edge between any pair of vertices.)Descriptive Explanation |

Question 14 Explanation:

We will call a sequence graphical if it consists of the degrees of all the vertices in a graph. Thus the question asks for an algorithm to test whether a given nonincreasing sequence of length n is graphical. By the Havell-Hakimi theorem, a nonincreasing
sequence s = (d

Algorithm 1 Algorithm to check if a nonincreasing sequence is graphical

function IsGraphical(s)

Let the input sequence be s = (d

if d

_{ 1}, d_{2}, . . . , d_{ n}) is graphical if and only if the sequence s 0 = (d_{2}− 1, d_{ 3}− 1, . . . , d_{d 1}+1 − 1, d_{d 1}+2 , . . . , d n ) is graphical. Noting that s 0 is a sequence of length n − 1, we are led to Algorithm 1.Algorithm 1 Algorithm to check if a nonincreasing sequence is graphical

function IsGraphical(s)

Let the input sequence be s = (d

_{1}, d_{ 2}, . . . , d_{n})if d

_{ 1}= d 2 = · · · = d_{ n<>/sub> = 0 then return true else if n = 1 and d 1 > 0 then return false else Form the sequence s s' = (d 2 − 1, d 3 − 1, . . . , d d 1 +1 − 1, d d 1 +2 , . . . , d n ) Let s 00 be s 0 sorted in descending order return IsGraphical(s' ' ) end if end function There are n recursive calls to the function IsGraphical, and the majority of the time in each call is spent in sorting the input sequence. Thus the algorithm takes time O(n 2 log n). }Question 15 |

An airline runs flights between several cities of the world. Every flight connects two cities. A millionaire wants to travel from Chennai to Timbuktu by changing at most k − 1 flights. Being a millionaire with plenty of time and money, he does not mind
revisiting the same city multiple times, or even taking the same flight multiple times in his quest. Can you help the millionaire by describing how to compute the number of ways he can make his journey? How many steps does your procedure take if there are n cities and he can change flights at most k − 1 times. You can assume that the procedure can add or multiply two numbers in a single operation.

Descriptive Explanation |

Question 15 Explanation:

Let c denote Chennai and t denote Timbuktu. We are asked to find the number of c, t-walks with at most k edges. For any city v, let N (v, i) denote the number of c, v-walks with exactly i edges. It is clear that N (c, 0) = 1 and N (v, 0) = 0 for any v 6 = c. To go from c to v in exactly i + 1 steps, one can choose to go to any u such that (u, v) ∈ E in exactly i steps, and then go to v in one more step. The following recurrence is thus easy to see.

We can create a two-dimensional with nk entries, and fill them in according to the above recurrence. The desired answer is given by N (t, 0) + N (t, 1) + · · · + N (t, k).

We need to fill in nk entries, and we add at most n numbers to compute each entry. Since adding two numbers is assumed to take unit time, we can add n numbers in O(n) time. Thus the overall time taken by the algorithm is O(n

We can create a two-dimensional with nk entries, and fill them in according to the above recurrence. The desired answer is given by N (t, 0) + N (t, 1) + · · · + N (t, k).

We need to fill in nk entries, and we add at most n numbers to compute each entry. Since adding two numbers is assumed to take unit time, we can add n numbers in O(n) time. Thus the overall time taken by the algorithm is O(n

^{2}k).Question 16 |

Consider the code below, defining the functions f and g:
f(m, n) {
if (m == 0) return n;
else {
q = m div 10;
r = m mod 10;
return f(q, 10*n + r);
}
}
g(m, n) {
if (n == 0) return m;
else {
q = m div 10;
r = m mod 10;
return g(f(f(q, 0), r), n-1);
}
}
(a) Compute g(3, 7), g(345, 1), g(345, 4) and g(345, 0).
(b) What does g(m, n) compute, for nonnegative numbers m and n?
(c) How much time does it take to compute f (m, n) and g(m, n)?

Descriptive Explanation |

Question 16 Explanation:

In the following, by “reverse of a number a” we mean the number got by reversing the digits of a.

We first prove by induction on the number of digits in m that the result of f (m, n) is the reverse of m appended to n.

• If m = 0, then f (m, n) = n, as we require.

• If m < 10, then q = 0 and r = m, and a recursive call is made to f (0, 10n + m) = 10n + m, which is the reverse of the digits of m appended to n.

• If m > 10, then r is the last digit of m, and q is all the other digits. There is a recursive call to f (q, 10n + r), whose output (by induction hypothesis applied on q, which has one fewer digit than m) is the reverse of q appended to 10n + r, which is exactly the reverse of m appended to n.

Now f (a, 0) is the reverse of a, and f (f (a, 0), b) is the reverse of reverse of a appended to b, or in other words, a appended to b. Thus g(m, 1) appends to the last digit of m the other digits of m—performing a right rotate of m, in other words. g(m, n) is just n right rotates performed on m.

It follows that g(3, 7) = 3, g(345, 1) = 534 and g(345, 0) = 345.

It is also easy to see from the code that f (m, n) takes O(log m) time and g(m, n) takes O(n · log m) time.

We first prove by induction on the number of digits in m that the result of f (m, n) is the reverse of m appended to n.

• If m = 0, then f (m, n) = n, as we require.

• If m < 10, then q = 0 and r = m, and a recursive call is made to f (0, 10n + m) = 10n + m, which is the reverse of the digits of m appended to n.

• If m > 10, then r is the last digit of m, and q is all the other digits. There is a recursive call to f (q, 10n + r), whose output (by induction hypothesis applied on q, which has one fewer digit than m) is the reverse of q appended to 10n + r, which is exactly the reverse of m appended to n.

Now f (a, 0) is the reverse of a, and f (f (a, 0), b) is the reverse of reverse of a appended to b, or in other words, a appended to b. Thus g(m, 1) appends to the last digit of m the other digits of m—performing a right rotate of m, in other words. g(m, n) is just n right rotates performed on m.

It follows that g(3, 7) = 3, g(345, 1) = 534 and g(345, 0) = 345.

It is also easy to see from the code that f (m, n) takes O(log m) time and g(m, n) takes O(n · log m) time.

Question 17 |

There is a thin, long and hollow fibre with a virus in the centre. The virus occasionally becomes active and secretes some side products. The fibre is so thin that new side products secreted by the virus push the old products along the fibre towards its ends.
The possible actions of the virus are as follows
(a) Produce an acid molecule to its left and a base molecule to its right.
(b) Produce a base molecule to its left and an acid molecule to its right.
(c) Divide into two viruses, each of which continues to behave like its ancestor.
(d) Die.
You are given a sequence of acid and base molecules from one end of the fibre to the other end. Design an algorithm to check if a single virus could possibly have produced the given sequence. Use dynamic programming, checking smaller subsequences before
checking bigger subsequences.

Descriptive Explanation |

Question 17 Explanation:

The language of the above grammar is the set of strings consisting of equal number of a’s and b’s.

A sequence of acid and base molecules is just a string over {a, b}. To check if a single virus could have produced the sequence, you can use CYK algorithm to check membership in the above context-free grammar.

There are 17 questions to complete.