You are here: Home > Entrance Exam
All posts from

# CMI M.Sc/Ph.D Computer Science Entrance Exam 2019 Question Paper

Organisation : Chennai Mathematical Institute
Exam : M.Sc/Ph.D Computer Science Entrance Exam
Document Type : Question Paper
Year : 2019

Contents :

## CMI M.Sc Entrance Question Paper

The entrance examination is a test of aptitude for Computer Science featuring both multiple choice questions and problems requiring detailed solutions drawn mostly from the following topics: discrete mathematics, algorithms, basic computer organization and some programming.

Related / Similar Question Paper : CMI M.Sc/Ph.D Computer Science Entrance Exam 2020 Question Paper

## M.Sc Computer Science Entrance Question Paper

1. Let A be an NFA with n states.Which of the following is necessarily true?
(a) The shortest word in L(A) has length at most n-1.
(b) The shortest word in L(A) has length at least n.
(c) The shortest word not in L(A) has length at most n-1.
(d) The shortest word not in L(A) has length at least n.

2. Suppose you alternate between throwing a normal six-sided fair die and tossing a fair coin. You start by throwing the die. What is the probability that you will see a 5 on the die before you see tails on the coin?
(a) 1/12
(b) 1/6
(c) 2/9
(d) 2/7

3. An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match requires a team of referees and linesmen.

Two matches that overlap require disjoint teams of referees and linesmen. The tournament organizers would like to determine how many teams of referees and linesmen they need to mobilize toeectively conduct the tournament. To determine this, which graph theoretic problem do the organizers have to solve?

(a) Find a minimal colouring.
(b) Find a minimal spanning tree.
(c) Find a minimal cut.
(d) Find a minimal vertex cover.

4. We have constructed a polynomial time reduction from problem A to problem B. Which of the following is not a possible scenario?

(a) We know of polynomial time algorithms for both A and B.
(b) We only know of exponential time algorithms for both A and B.
(c) We only know an exponential time algorithm for A, but we have a polynomial time algorithm for B.
(d) We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.

5. When the procedure terminates, the array A has been:
(a) Sorted in descending order
(c) Reversed
(b) Sorted in ascending order
(d) Left unaltered

6. The number of times the test A[j] > A[m] is executed is:
(a) 4950
(b) 5050
(c) 10000
(d) Depends on the contents of A