1. Let G = ({S), {a, b} R, S) be a context free grammar where the rule set R is

S ® a S b |S S l e

Which of the following statements is true?

(a) G is not ambiguous

(b) There exist x, y, Î L (G) such that xy Ï L(G)

(c) There is a deterministic pushdown automaton that accepts L(G)

(d) We can find a deterministic finite state automaton that accepts L(G)

2. Consider two languages L 1 and L 2 each on the alphabet å . Let f: å ® å be a

polynomial time computable bijection such that ( " x) [x Î L 1 iff f(x) Î L 2].Further,

let f -l be also polynomial time computable..

Which of the following CANNOT be true ?

(a) L 1 Î P and L 2 is finite

(b) L 1 Î NP and L 2 Î P

(c) L 1 is undecidable and L 2 is decidable

(d) L 1 is recursively enumerable and L 2 is recursive

3. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table

The table is interpreted as illustrated below.

The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?

(a) M does not halt on any string in (0 + 1) +

(b) M does not halt on any string in (00 + 1)*

(c) M halts on all string ending in a 0

(d) M halts on all string ending in a 1

4. Define languages L 0 and L 1 as follows:

L 0 = {<M, w,O> I M halts on w}

L 1 = {<M, w, 1> I M does not halts on w}

Here <M, w, i> is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit, Let L = L 0 È L 1. Which of the following is true?

(a) L is recursively enumerable, but is not

(b) is recursively enumerable, but L is not

(c) Both Land L are recursive

(d) Neither L nor is recursively enumerable

5. Consider the NFA M shown below.

Let the language accepted by M be L. Let L 1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?

• L 1 = {O, 1}* - L
• L 1 = {O, 1}*
• L 1 Í L
• L 1 = L

6. Consider the grammar shown below

S ® i E t S S ' l a

S' ® e S | e

E ® b

In the predictive parse table. M, of this grammar, the entries M[S', eJ and M[S ’, $] respectively are

(a) {S' ® e S} and {S' ® e } (b) {S' ® e S} and {}

(c) {S' ® e } and {S' ® e } (d) {S' ® e S, S' ® e } and {S' ® e }

7. Consider the grammar shown below.

S ® CC

C ® cC | d

The grammar is

• LL (1)
• SLR (1) but not LL (1)
• LALR (1) but not SLR (1)
• LR (1) but not LALR (1)

8. Consider the translation scheme shown below

S ® TR

R ® + T {print ('+');} R | e

T ® num {print (num.val);}

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string '9 + 5 + 2’, this translation scheme will print

• 9 + 5 + 2
• 9 5 + 2 +
• 9 5 2 + +
• + + 9 5 2

9. Consider the syntax directed definition shown below.

S ® id : = E {gen (id.place = E.place;);}

E ®E 1 + E 2 {t = newtemp ( );

gen (t = E 1. place + E 2.place;);

E.place = t}

E ® id {E.place = id.place;}

Here, gen is a function that generates the output code, and newtemp is a function that returns the name of a new temporary variable on every call. Assume that t i's are the temporary variable names generated by newtemp.

For the statement 'X: = Y + Z', the 3-address code sequence generated by this definition is

(a) X = Y + Z

(b) t 1 = Y + Z; X t 1

(c) t 1 = Y; t 2 = t 1 + Z; X = t2

(d) t 1 = Y; t 2 = Z; t 3 = t 1 + t 2; X = t 3

10. A program consists of two modules executed sequentially. Let f 1(t) and f 2(t) respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by

• f 1 (t) + f 2(t)
• 
• 
• max {f 1(t), f 2(t)}

THE FOLLOWING INFORMATION PERTAINS TO Q. 61-62

In a permutation a 1…a n of n distinct integers, an inversion is a pair (a i, a j) such that i <j and a i >a j

11. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1...n ?

(a) n(n -1)/2 (b) n(n -1)/4

(c) n(n + 1)/4 (d) 2n[log2n]

12. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1...n with at most n inversions?

(a) Q (n 2) (b) Q (n log n)

(c) Q (n 1.5) (d) Q (n)

13. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

• Delection of the smallest element
• Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

(a) A heap can be used but not a balanced binary search tree

(b) A balanced binary search tree can be used but not a heap

(c) Both balanced binary search tree and heap can be used

(d) Neither balanced binary search tree nor heap can be used

14. Let S be a stack of size n ³ 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the Blurt of the next operation. For m ³ 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

• n (X+ Y)
• 3Y + 2X
• n (X+ Y)-X
• Y + 2X

15. Consider the following 2-3-4 tree (i.e., B-tree with a minimum degree of two) in which each data item is a letter. The usual alphabetical ordering of letters is used in constructing the tree

What is the result of inserting G in the above tree ?

(a)

(b)

(c)

(d) None of the above

16. The cube root of a natural number n is defined as the largest natural number m such that m 3 £ n. The complexity of computing the cube root of n (n is represented in binary notation) is

• O(n) but not O(n 0.5)
• O(n 0.5) but not O ((log n) k) for any constant k > 0
• O ((log n) k) for some constant k > 0, but not O ((log log n) m) for any constant m > 0
• O ((log log n) k) for some constant k > 0.5, but not O ((log log n) 0.5)

17. Let G = (V, E) be an undirected graph with a sub graph G 1 = (V 1, E 1). Weights are assigned to edges of G as follows:

A single-source shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex v 1 of V 1 as the source. Which of the following can always be inferred from the path costs computed?

• The number of edges in the shortest paths from V 1 to all vertices of G
• G 1 is connected
• V 1 forms a clique in G
• G 1 is a tree

18. What is the weight of a minimum spanning tree of the following graph?

• 29
• 31
• 38
• 41

19. The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: "a s b s a s a e d s a e e s f s b e d e g s e e f e h s g e h e". Here, x s denotes the starting time and X e denotes the ending time of activity X. W need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?

(a) 3 (b) 4

(c) 5 (d) 6

20. Let G = (V, E) be a directed graph with n vertices. A path from V i to V j in G is sequence of vertices (V i, v i+1, ..., V j) such that (V k, V k+1) Î E for all k in i through j -1. A simple path is a path in which no vertex appears more than once.

Let A be an n x n array initialized as follow

Consider the following algorithm.

for i = 1 to n

for j = 1 to n

for k = 1 to n

A [j, k] = max (A[j, k] (A[j,i] + A [i, k]);

Which of the following statements is necessarily true for all j and k after terminal of the above algorithm?

• A[j,k] £ n
• If A [j, j] ³ n - 1, then G has a Hamiltonian cycle
• If there exists a path from j to k, A[j, k] contains the longest path lens from j to k
• If there exists a path from j to k, every simple path from j to k contain most A[j, k] edges