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

 Question 1
For the inter-hostel six-a-side football tournament, a team of 6 players is to be chosen from 11 players consisting of 5 forwards, 4 defenders and 2 goalkeepers. The team must include at least 2 forwards, at least 2 defenders and at least 1 goalkeeper. Find the number of different ways in which the team can be chosen.
 A 260 B 340 C 720 D 1440
Engineering-Mathematics       Combinatorics
Question 1 Explanation:
5 positions are fixed. The 6th can be forward/defender/goalkeeper. Question 2
The 12 houses on one side of a street are numbered with even numbers starting at 2 and going up to 24. A free newspaper is delivered on Monday to 3 different houses chosen at random from these 12. Find the probability that at least 2 of these newspapers are delivered to houses with numbers strictly greater than 14.
 A 7/11 B 5/12 C 4/11 D 5/22
Engineering-Mathematics       Probability
Question 2 Explanation:  Question 3
In the code fragment on the right, start and end are integer values and prime(x) is a function that returns true if x is a prime number and false otherwise. i := 0; j := 0; k := 0; for (m := start; m <= end; m := m+1){ k := k + m; if (prime(m)){ i := i + m; }else{ j := j + m; } } At the end of the loop:
 A k < i+j B k = i+j C k > i+j D Depends on start and end
Programming       Control-Statement
Question 3 Explanation:
In each iteration, the value added to k is also added to exactly one of i and j.
 Question 4
Alan’s task is to design an algorithm for a decision problem P . He knows that there is an algorithm A that transforms instances of P to instances of the Halting Problem such that yes instances of P map to yes instances of the Halting Problem, and no instances of P map to no instances of the Halting problem. Which of the following is true.
 A The existence of A implies the existence of an algorithm for P . B The existence of A implies that there is no algorithm for P . C The existence of A says nothing about whether there is an algorithm for P . D The Halting Problem can be solved using A.
Theory-of-Computation       Turing-machines
Question 4 Explanation:
The reduction is from P to the Halting Problem, so we cannot infer undecidability of P .
There are 4 questions to complete.

Register Now