CMI Entrance Exam MSc/PhD Computer Science Question Paper : Chennai Mathematical Institute
Name of the Organisation : Chennai Mathematical Institute
Exam : Entrance Exam
Subject : MSc/PhD Computer Science
Year : 2016
Document Type : Previous Years’ Question Papers
Website : http://www.cmi.ac.in/admissions/syllabus.php
Download Model/Sample Question Paper :
MSc/PhD Computer 2010 : https://www.pdfquestion.in/uploads/13295-pgcs2010.pdf
MSc/PhD Computer 2011 : https://www.pdfquestion.in/uploads/13295-pgcs2011.pdf
MSc/PhD Computer 2012 : https://www.pdfquestion.in/uploads/13295-pgcs2012.pdf
MSc/PhD Computer 2013 : https://www.pdfquestion.in/uploads/13295-pgcs2013.pdf
MSc/PhD Computer 2014 : https://www.pdfquestion.in/uploads/13295-pgcs2014.pdf
MSc/PhD Computer 2015 : https://www.pdfquestion.in/uploads/13295-pgcs2015.pdf
MSc/PhD Computer 2016 : https://www.pdfquestion.in/uploads/13295-pgcs2016.pdf
CMI MSc/PhD Computer Science Question Paper
Instructions :
1. This question paper has 5 printed sides.
2. Part A has 10 questions of 3 marks each.
Related : Chennai Mathematical Institute Entrance Examination for BSc Maths & Computer Question Paper : www.pdfquestion.in/13290.html
3. Part B has 7 questions of 10 marks each.
4. The total marks are 100. Answers to Part A must be filled in the answer sheet provided.
Part A
1. In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote by P the following property: there exists a vertex that is a neighbour of all other vertices.Consider the following statements
(i) If P is false, then there is a pair of vertices such that the distance between them is at least 4.
(ii) If P is true, then the distance between any pair of vertices is at most 2.
What can you say about these statements?
(a) Only (i) is true.
(c) Both (i) and (ii) are true.
(b) Only (ii) is true.
(d) Neither (i) nor (ii) is true.
2. The symbol j reads as \divides”, and – as \does not divide”. For instance, 2 j 6 and 2 – 5 are both true. Consider the following statements:
(i) There exists a positive integer a such that (2 j (a3+ 1)) and (2j- a).
(ii) There exists a positive integer b such that 6 – (b3 +b).
What can you say about these statements?
(a) Only (i) is true.
(c) Both (i) and (ii) are true.
(b) Only (ii) is true.
(d) Neither (i) nor (ii) is true.
3. For a regular expression e, let L(e) be the language generated by e. If e is an expression that has no Kleene star occurring in it, which of the following is true about e in general?
(a) L(e) is empty.
(b) L(e) is nite.
(c) Complement of L(e) is empty.
(d) Both L(e) and its complement are innite.
4. Consider a weighted undirected graph G with positive edge weights. Let (u; v) be an edge in the graph. It is known that the shortest path from a vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which of the statements is always true?
(a) Weight of (u; v) 12.
(b) Weight of (u; v) = 12.
(c) Weight of (u; v) 12.
(d) Nothing can be said about the weight of (u; v).
5. A dodecahedron is a regular solid with 12 faces, each face being a regular pentagon. How many edges are there? And how many vertices?
(a) 60 edges and 20 vertices.
(c) 60 edges and 50 vertices.
(b) 30 edges and 20 vertices.
(d) 30 edges and 50 vertices.
6. In the code fragment to 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.
At the end of the loop:
(a) k == i-j.
(b) k == j-i.
(c) k == -j-i.
(d) Depends on start and end.
7. Varsha lives alone and dislikes cooking, so she goes out for dinner every evening. She has two favourite restaurants, Dosa Paradise and Kababs Unlimited, to which she travels by local train. The train to Dosa Paradise runs every 10 minutes, at 0, 10, 20, 30, 40 and 50 minutes past the hour. The train to Kababs Unlimited runs every 20 minutes, at 8, 28 and 48 minutes past the hour. She reaches the station at a random time between 7:15 pm and 8:15 pm and chooses between the two restaurants based on the next available train. What is the probability that she ends up eating in Kababs Unlimited?
(a) 1/5
(b) 1/3
(c) 2/5
(d) 1/2
8. An advertisement for a tennis magazine states, \If I’m not playing tennis, I’m watching tennis. And if I’m not watching tennis, I’m reading about tennis.” We can assume that the speaker can do at most one of these activities at a time. What is the speaker doing?
(a) Playing tennis.
(c) Reading about tennis.
(b) Watching tennis.
(d) None of the above.
9. ScamTel has won a state government contract to connect 17 cities by high-speed bre optic links. Each link will connect a pair of cities so that the entire network is connected|there is a path from each city to every other city. The contract requires the network to remain connected if any single link fails. What is the minimum number of links that ScamTel needs to set up?
(a) 34
(b) 32
(c) 17
(d) 16
10. Which of the following relationships holds in general between the scope of a variable and the lifetime of a variable (in a language like C or Java)?
(a) The scope of a variable is contained in the lifetime of the variable.
(b) The scope of a variable is the same as the lifetime of the variable.
(c) The lifetime of a variable is disjoint from the scope of the variable.
(d) None of the above.
Part B
1. An international cellphone company provides service on 7 different frequencies. They wish to set up business in Tamil Nadu and have fixed the locations of 100 towers for their new service. The company has to ensure that two towers broadcasting on the same frequency are at least 100 km apart, so that there is no interference of signals.
(i) Model this problems using graphs.
(ii) Describe an algorithm which will answer the question “Is it feasible to set up towers at the given locations and provide service on 7 different frequencies?”. Youralgorithm should say “feasible” if it is feasible, otherwise output the minimum number of frequencies needed to utilise all 100 towers.
2. Let G be a graph in which each vertex has degree at least k. Show that there is a path of length k in G—that is, a sequence of k+1 distinct vertices v0, v1, …, vk such that for 0 i < k, vi is connected to vi+1 in G.
3. The Income-Tax Department had prepared a list D of names of defaulters on March 31. However, the government extended the deadline to pay taxes till April 15. The IT department has now received two additional lists of names: a list B of namesof people who have paid their taxes between April 1 and April 15 at a bank, and a list O of names of people have paid their taxes during this period online. Some people have paid part of their taxes at a bank and part online, so there may be names that appear in both B and O.
From the lists D, B and O, the IT department wants to prepare a revised list of defaulters. The names in the original list D are sorted in alphabetical order while thenames in B and O are listed according to the date on which they paid their taxes. Fortunately, no two people have the same name.
Describe an efficient algorithm to compute the revised list of defaulters. Assume that the size of D, B and O is n, m and k respectively and that n > m > k. Describe the running time of your algorithm in terms of these parameters.
4. Indicate whether the following statements are true or false, providing a short explana- tion to substantiate your answers.
(i) A DFA with n states must accept at least one string of length greater than n.
(ii) A DFA that has n states and accepts an infinite language must accept at least one string x such that 2n < |x| < 3n, where |x| denotes the length of x.
(iii) If a language L is accepted by an NFA with n states then there is a DFA with no more than 2n states accepting L.
5. Sales have slumped at the Siruseri noodle factory and the management may need to terminate the contracts of some employees. Every employee has one immediate boss. The seniormost person in the company is the president, who has no boss.
For legal reasons, if an employee’s contract is not terminated, then his boss’s contract cannot be terminated either. For how many different sets of employees can the management legally terminate contracts? Note that one possibility that has to be counted explicitly is that no employees’ contracts are terminated (that is, the set of employees whose contract is terminated is the empty set).