# Sample questions - M.Sc. / Ph.D entrance examination : Computer

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 (b) 50 (c) 105 (d) 510

3. Consider the following two programs, operating on an array A of n

integers:

Program I:

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

Program II:

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