Organisation : Chennai Mathematical Institute
Exam : M.Sc/Ph.D Computer Science Entrance Exam
Document Type : Question Paper
Year : 2020
Website : https://www.cmi.ac.in/admissions/syllabus.php
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 2019 Question Paper
M.Sc Computer Science Entrance Question Paper
1. Which of the following languages over the alphabet {0, 1} are not recognized by deterministic finite state automata (DFA) with three states?
(a) Words which do not have 11 as a contiguous subword
(b) Binary representations of multiples of three
(c) Words that have 11 as a suffix
(d) Words that do not contain 101 as a contiguous subword
2. Consider the following regular expressions over alphabet {a, b}, where the notation (a + b)+ means (a + b)(a + b)* :
r1 = (a + b)+ a (a + b)*
r2 = (a + b)* b (a + b)+
Let L1 and L2 be the languages defined by r1 and r2, respectively. Which of the following regular expressions define L1 n L2?
(a) (a + b)+ a (a + b)* b (a + b)+
(c) (a + b)* b (a + b)* a (a + b)*
(b) (a + b)* a b (a + b)*
(d) (a + b)* a (a + b)* b (a + b)*
3. Some children are given boxes containing sweets. Harish is happy if he gets either gems or toffees. Rekha is happy if she gets both bubble gums and peppermints. Some of the boxes are special, which means that if the box contains either gems or toffees, then it also contains bubble gums and peppermints. If Harish and Rekha are given boxes that are not special, which of the following can we infer?
(a) Harish is happy
(b) No bubble gums in Rekha’s box
(c) No toffees in Harish’s box
(d) There are peppermints in Rekha’s box
4. In a class, every student likes exactly one novelist and one musician. If two students like the same novelist, they also like the same musician. The class can be divided into novelist groups, each group consisting of all students who like one novelist. Similarly, musician groups can be formed. So each student belongs to one musician group and one novelist group. Which of the following is a valid conclusion?
(a) There are more musician groups than novelist groups
(b) There are at least as many novelist groups as musician groups
(c) For every musician group, there is a bigger novelist group
(d) For every novelist group, there is a musician group of the same size
5. The next two questions are based on the following facts. Basketball shots are classified into close-range, mid-range and long-range shots. Long range shots are worth 3 points, while close-range and mid-range shots are worth 2 points. Of the shots that LeBron James attempts, 45% are close-range, 25% are mid-range, and 30% are long-range. He successfully makes 80% of the close-range shots, 48% of the mid-range shots, and 40% of the long-range shots.
What is the probability that a LeBron shot attempt is successful?
(a) 1/2
(b) 4/5
(c) 3/5
(d) 4/7
What is the probability that a successful 2-point shot attempt by LeBron is a closerange shot?
(a) 2/5
(b) 3/5
(c) 3/7
(d) 3/4
6. We have a procedure P(n) that makes multiple calls to a procedure Q(m), and runs in polynomial time in n. Unfortunately, a significant flaw was discovered in Q(m), and it had to be replaced by R(m), which runs in exponential time in m. Thankfully, P is still correct when we replace each call to Q(m) with a call to R(m) instead. Which of the following can we definitely say about the modified version of P?
(a) P(n) still runs in polynomial time in n.
(b) P(n) requires exponential time in n.
(c) P(n) runs in polynomial time in n if the number of calls made to Q is proportional to log n.
(d) P(n) runs in polynomial time in n if, for each call Q(m), m = log n.
Download Question Paper
M.Sc/Ph.D Computer Science Entrance Question Paper : https://www.pdfquestion.in/uploads/pdf2021/37261-mcs20.pdf