BSc/MSc/PhD Entrance Exam Question Paper Admissions 2015 cmi.ac.in : Chennai Mathematical Institute

Organization : Chennai Mathematical Institute
Entrance Exam : CMI Admissions 2015 Entrance Exam
Facility : Question Paper

Question Paper : http://www.cmi.ac.in//admissions/syllabus.php
Home Page : http://cmi.ac.in/

BSc (Hons) Mathematics and Computer Science : https://www.entrance.net.in/uploads/931-ugmath2010.pdf
MSc/PhD Computer Science : https://www.entrance.net.in/uploads/931-pgcs2010.pdf
MSc/PhD Mathematics : https://www.entrance.net.in/uploads/931-pgmath2010.pdf
MSc Applications of Mathematics : https://www.entrance.net.in/uploads/931-mscappmath2010.pdf
PhD Physics : https://www.entrance.net.in/uploads/931-pgphysics2011.pdf

M.Sc. / Ph.D Question Paper :

Entrance Examination, 15 May 2014
This question paper has 4 printed sides. Part A has 10 questions of 3 marks each. Part B has 7 questions of 10 marks each.

Related :

CMI BSc/MSc/PhD Entrance Exam Syllabus : www.entrance.net.in/930.html

The total marks are 100. Answers to Part A must be lled in the answer sheet provided.

Part A :
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 dierent ways in which the team can be chosen.
(a) 260 (b) 340 (c) 720 (d) 1440

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 dierent 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.

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.

Suppose we are working with a programming language that supports automatic garbage collection. This means that:
(a) Uninitialized variables are assigned null values.
(b) Unreferenced dynamically allocated memory is added back to free space.
(c) Unreachable if-then-else branches are pruned.
(d) Expressions where array indices exceed array bounds are agged.

A company is due to send a shipment to a client and the CEO has resigned. To select a new CEO, some candidates have been interviewed. One of them will be chosen through a vote. If the workers union resort to a strike and the candidates have to be interviewed again, then the shipment deadline will be missed. If there are more abstainers than voters in the vote to choose the new CEO, then the candidates have to be interviewed again. Suppose that the shipment was sent on time. Which of the following is a valid conclusion?
(a) The workers union did not resort to a strike.
(b) The number of voters was more than the number of abstainers.
(c) (a) or (b).

If the workers union resorted to a strike, then the number of voters was greater than or equal to the number of abstainers.

Avinash is taller than Abhay. Bharat is taller than Vinu and Vinay is taller than Bharat. Which of the following is a minimal set of additional information that can determine the tallest person?
(a) Vinay is taller than Avinash and Abhay is taller than Bharat.
(b) Avinash is taller than Vinay.
(c) Abhay is shorter than Vinay.
(d) None of the above.

Part B :
2. There are n students in a class. The students have formed k committees. Each committee consists of more than half of the students. Show that there is at least one student who is a member of more than half of the committees.

3. Air CMI operates direct lights between dierent cities. For any pair of cities A and B, there is at most one ight in a day from A to B. The online site FakeTrip is trying to compile a list of all routes available through Air CMI.

(a) FakeTrip has a table of all direct ights operated by Air CMI. From this, it wants to prepare a list of all pairs of cities connected by a sequence of ights. Describe an algorithm for this and analyze the complexity of your algorithm.

(b) CheapTricks is trying to enter the market by improving on FakeTrip. CheapTricks has realized that not all connections listed by FakeTrip are feasible because of arrival and departure constraints. A connection from A to B to C is possible if the scheduled arrival of the ight from A to B is at least one hour before the scheduled departure of the ight from B to C.

Given a table of direct ights with scheduled arrival and departure times, describe an algorithm for CheapTricks to list all pairs of cities connected by a route on which all connections are feasible within the same day. Analyze the complexity of your algorithm.

4. The frequency of a number in an array is the number of times it appears in the array. Describe an algorithm that nds the most frequent number in an array of n numbers. If there are multiple numbers with highest frequency then list them all. Analyze the complexity of your algorithm.