Cmi.sample Qp

Sample questions - M.Sc. / Ph.D entrance examination : Computer Science. 1. If Jogesh’s program runs correctly, he is happy. Which of the following statements is true? (a) If Jogesh’s program does not run correctly, he is not happy. (b) If Jogesh is happy, his program must have run correctly. (c) If Jogesh is not happy, his program must not have run correctly. (d) None of the above 2. Let X and Y be two sets such that |X| = 10 and |Y | = 5. Let S be the set of all injective (i.e., 1–1) functions from X to Y . What is |S|? (a) 0

(c) 105

(b) 50

(d) 510

3. Consider the following two programs, operating on an array A of n integers: Program I:

Program II:

M = A(1) For i = 2 to n If A(i) > M Then M = A(i) Endif EndFor Count = 0 For i = 1 to n If A(i) = M Then Count = Count + 1 Endif EndFor Output Count

If A(1) = A(n) Then Count = n Else i=1 While (A(i) < A(n)) Do i=i+1 EndWhile Count = n − i + 1 Endif Output Count

(i) Which program correctly counts the number of occurrences of the maximum element in the array? (a) I (b) II (c) I and II (d) neither (ii) Which program correctly counts the number of occurrences of the maximum element in the array, if the array is sorted in increasing order? 1

(a) I

(b) II

(c) I and II

(d) neither

4. A queue is a list with insertions at the end and deletions from the head. The following list of operations is performed on an empty queue: INSERT A, INSERT B, DELETE, INSERT C, INSERT A, DELETE, INSERT D, DELETE. (i) What element is deleted by the last DELETE instruction? (ii) What are the contents of the queue after this sequence of instructions? 5. Is the language consisting of binary strings, whose last three bits are 011, regular? If yes, construct a finite automaton accepting this language. If no, provide a proof that the language is not regular. 6. Show that any tree with n vertices has exactly n − 1 edges. 7. Describe the avantages of 2’s complement representation over the sign magnitude representation. Represent the following integers, if possible, in 8-bit 2’s complement notation (a) 113 (b) -127 8. Given a sequence of integers a1 , . . . , an , an increasing subsequence is a sequence of the form ai1 , ai2 . . . , aik such that ai1 ≤ ai2 . . . ≤ aik and i1 ≤ i2 . . . ≤ ik . Describe an algorithm that computes the length of the longest increasing subsequence in a given array.

2