Time Allowed: 3 Hours Maximum Marks: 150

Read the following instructions carefully

1. This question paper contains 90 objective questions. Q. 1-30 carry one mark each and Q.31-90 carry two marks each.
2. Answer all the questions.
3. Questions must be answered on special machine gradable Objective Response Sheet (ORB) by darkening the appropriate bubble (marked A, B, C, D) using HB pencil against the question number on the left hand side of the ORS. Each question has only one correct answer. In case you wish to change an answer, erase the old answer completely using a good soft eraser.
4. There will be NEGATIVE marking. For each wrong answer 0.25 mark from Q. 1-30 and 0.5 mark from Q. 31-90 will be deducted. More than one answer marked against a question will be deemed as an incorrect response and will be negatively marked.
5. Write your registration number, name and name of the Centre at the specified locations on the right half of the ORB.
6. Using HB pencil, darken the appropriate bubble under each digit of your registration number.
7. Using HB pencil, darken the appropriate bubble under the letters corresponding to your paper code.
8. No charts or tables are provided in the examination hall.
9. Use the blank pages given at the end of the question paper for rough work.
10. Choose the closest numerical answer among the choices given.
11. This question paper contains 24 pages. Please report if there is any discrepancy.

Q. 1 - 30 CARRY ONE MARK EACH

1. Consider the following C function.

float f,(float x, int y) {

float p, s; int i;

for (s=1, p=1, i=1; i < y; i ++) {

p*= x/i;

s+=p;

}

return s;

}

For large values of y, the return value of the function f best approximates

• X Y
• e x
• ln (1 + x)
• X X

2. Assume the following C variable declaration

int *A [10], B [10][10];

Of the following expressions

• A[2]
• A [2] [3]
• B [1]
• B [2] [3]

which will not give compile-time errors if used as left hand sides of assignment statements in a C program ?

• I, II, and IV only
• II, III, and IV only
• II and IV only
• IV only

3. Let P(E) denote the probability of the event E. Given P(A)= 1, P(B) = 1/2, the values of P(A \ B) and P(B / A) respectively are

• ¼, ½
• ½, ¼
• ½, 1
• 1, ½

1. Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, Band C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 8 elements, and (iii) the result of merging B and C gives A ? .

• 2
• 30
• 56
• 256

5. n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is

(a)

• 3 n
• (2n)!

2 n

6. Let T(n) be the number of different binary search trees on n distinct elements.

Then T(n) = where x is

• n - k + 1
• n - k
• n - k – 1
• n - k - 2

7. Consider the set å * of all strings over the alphabet å = (0, 1). å * with the concatenation operator for strings

• does not form a group
• forms a non-commutative group
• does not have a right identity element
• forms a group if the empty string is removed from å *

8. Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between

• k and n
• k - 1 and k + 1
• k - 1 and n - 1
• k + 1 and n-k

9. Assuming all numbers are in 2's complement representation, which of the following numbers is divisible by 11111011 ?

• 11100111
• 11100100
• 11010111
• 11011011

10. For a pipelined CPU with a single ALU, consider the following situations

• The j + 1-st instruction uses the result of the j-th instruction as an operand
• The execution of a conditional jump instruction
• The j-th and j + 1-st instructions require the ALU at the same time

Which of the above can cause a hazard?

• I and II only
• II and III only
• III only
• All the three

11. Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

• Q (1)
• Q (log n)
• Q (n)
• Q (n 2)

12. Ram and Shyam have been asked to show that a certain problem Õis NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Õ, and Shyam shows a polynomial time reduction from Õ to 3-SAT. Which of the following can be inferred from these reductions?

• Õ is NP-hard but not NP-complete
• Õ is in NP, but is not NP-complete
• Õ is NP-complete
• Õ is neither NP-hard, nor in NP

13. Nobody knows yet if P = NP. Consider the language L defined as follows:

Which of the following statements is true?

• L is recursive
• L is recursively enumerable but not recursive
• L is not recursively enumerable
• Whether L is recursive or not will be known after we find out if P = NP

14. The regular expression 0* (10*)* denotes the same set as

• (1*0)*1*
• 0 + (0 + 10)*
• (0 + 1)* 10(0 + 1)*
• none of the above

15. If the strings of a language L .can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

(a) L is necessarily finite

(b) L is regular but not necessarily finite

(c) L is context free but not necessarily regular

(d) L is recursive but not necessarily context free

16. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar ?

(a) Removing left recursion alone

(b) Factoring the grammar alone

(c) Removing left recursion and factoring the grammar

(d) None of the above

17. Assume that the SLR parser for a grammar G has n 1 states and the LALR parser for G has n 2 states. The relationship between n l and n 2 is

(a) n 1 is necessarily less than n2

(b) n 1 is necessarily equal to n2

(c) n 1 is necessarily greater than n2

(d) none of the above

18. In a bottom-up evaluation of a syntax directed definition, inherited attributes can

(a) always be evaluated

(b) be evaluated only if the definition is L-attributed

(c) be evaluated only if the definition has synthesized attributes

(d) never be evaluated

19. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

• 7 5 1 0 3 2 4 6 8 9
• 0 2 4 3 1 6 5 9 8 7
• 0 1 2 3 4 5 6 7 8 9
• 9 8 6 4 2 3 0 1 5 7

20. Consider the following three claims

• (n + k) m = Q (n m), where k and m are constants
• 2 n + 1 = 0(2 n)
• 2 2n + 1 = 0(2 n)

Which of these claims are correct?

(a) I and II

(b) I and III

(c) II and III

(d) I, II and III

21. Consider the following graph

Among the following sequences

• a b e g h f
• a b f e h g
• a b f h g e
• a f g h b e

Which are depth first traversals of the above graph?

(a) I, II and IV only (b) I and IV only

(e) II, III and IV only (d) I, III and IV only

22. The usual Q (n2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

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

(e) become Q (n log n) (d) become Q (n)

23. In a heap with n elements with the smallest element at the root, the 7 th smallest element can be found in time

• Q (n log n)
• Q (n)
• Q (log n)
• Q (1)

24. Which of the following statements is FALSE?

(a) In statically typed language, each variable in a program has a fixed type

(b) In un-typed languages, values do not have any types

(c) In dynamically typed languages, variables have no types

(d) In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program

25. Using a larger block size in a fixed block size file system leads to

• better disk throughput but poorer disk space utilization
• better disk throughput and better disk space utilization
• poorer disk throughput but better disk space utilization
• poorer disk throughput and poorer disk space utilization

26. In a system with 32 bit virtual addresses and 1 KB page size, use of one-level page tables for virtual to physical address translation is not practical because of

(a) the large amount of internal fragmentation

(b) the large amount of external fragmentation

(c) the large memory overhead in maintaining page tables

(d) the large computation overhead in the translation process

27. Which of the following assertions is FALSE about the Internet Protocol (IP)?

(a) It is possible for a computer to have multiple IP addresses

(b) IP packets from the same source to the same destination can take different routes in

the network

(c) IP ensures that a packet is discarded if it is unable to reach its destination within a

given number of hops

(d) The packet source cannot set the route of an outgoing packets; the route is determined

only by the routing tables in the routers on the way

28. Which of the following functionalities must be implemented by a transport protocol over and above the network protocol?

(a) Recovery from packet losses

(b) Detection of duplicate packets

(c) Packet delivery in the correct order

(d) End to end connectivity

29. Which of the following scenarios may lead to an irrecoverable error in a database system?

• A transaction writes a data item after it is read by an uncommitted transaction
• A transaction reads a data item after it is read by an uncommitted transaction
• A transaction reads a data item after it is written by a committed transaction
• A transaction reads a data item after it is written by an uncommitted transaction

30. Consider the following SQL query

select distinct a 1. a 2, ...... , a n

from r 1, r 2……….., r m

where P

For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expressions?

(a)

(b)

(c)

(d)

31. Let (S, £ ) be a partial order with two minimal elements a and b, and a maximum element c. Let P : S ® {True, False} be a predicate defined on S. Suppose that p(a) = True, P(b) = False and P(x) Þ P(y) for all x, y Î S satisfying x £ y, where Þ stands for logical implication. Which of the following statements CANNOT be true?

(a) P(x) = True for all X Î S such that x ¹ b

(b) P(x) = False for all X Î S such that x ¹ a and x ¹ c

(c) P(x) = False for all X Î S such that b £ x and x ¹ c

(d) P(x) = False for all X Î S such that a £ and b £ x

32. Which of the following is a valid first order formula? (Here a and b are first order formulae with x as their only free variable)

(a) (( " x) [ a ] Þ ( " x)[ b ]) Þ ( " x) [ a Þ b ]

(b) ( " x) [ a ] Þ ( $ x) [ a Ù b ]

(c) (( " x) [ a v b ] Þ ( $ x)[ a ]) Þ ( " x) [ a ]

(d) ( " x) [ a Þ b ] Þ (( " x)[ a ] Þ ( " x) [ b ])

33. Consider the following formula a and its two interpretations I 1 and I 2

a: ( " x) [P x Û ( " y) [Q xy Û Ø Q yy]] ==> ( " x) [ Ø P x]

I 1: Domain: the set of natural numbers

P x == 'x is a prime number

Q xy == 'y divides x'

I 2: same as I 2 except that Px = 'x is a composite number'.

Which of the following statements is true?

(a) I 1 satisfies a , I 2 does not

(b) I 2 satisfies a , I 1 does not

(c) Neither I 1 nor I­ 2 satisfies a

(d) Both I 1 and I 2 satisfy a

34. m identical balls are to be placed in n distinct bags. You are given that m ³ kn, where k is a natural number ³ 1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?

(a)

(b)

(c)

(d)

35. Consider the following recurrence relation

T(1) = 1

T(n + 1) = T(n) + for all n ³ 1

The value of T(m 2) for m ³ 1 is

(a)

(b)

(c)

(d)

36. How many perfect matchings are there in a complete graph of 6 vertices?

• 15
• 24
• 30
• 60

37. Let f: A ® B be an injective (one-to-one) function. Define g: 2 A ® 2 B as:

g(C) = (f(x) \x Î C}, for all subsets C of A.

Define h: 2 B ® 2 A as: h(D) = { x\x Î A, f(x) Î D}, for all subsets D of B.

Which of the following statements is always true?

• g(h(D)) Í D
• g(h(D)) Ê D
• g(h(D)) Ç D = f
• g(h(D)) Ç (B-D) ¹ f

38. Consider the set {a, b, c} with binary operators + and x defined as follows:

+ a b c x a b c

a b a c a a b c

b a b c b b c a

c a c b c c c b

For example, a + c = c, c + a = a, c x b = c and b x c = a. Given the following set of equations:

(a x x)+(a x y)=c

(b x x)+(c x y)=c

the number of solution(s) (i.e., pair(s) (x, y) that satisfy the equations) is

(a) 0 (b) 1

(c) 2 (d) 3

39. Let å = (a, b, c, d, e) be an alphabet. We define an encoding scheme as follows:

g(a) = 3, g(b) = 5, g(c) = 7, g(d) = 9, g(e) = 11.

Let P i denote the i-th prime number (p 1 = 2)

For a non-empty string s = a 1...a n where each a i Î å , define f(s) = Õ n i= 1p i g(ai). For

a non-empty sequence (< Sl…Sn>) of strings from å + , define

h(<s l…s n>) = Õ n i = 1 p i f(si)

Which of the following numbers is the encoding, h of a non-empty sequence of strigs ?

• 2 73 75 7
• 2 83 85 8
• 2 93 95 9
• 2 105 107 10

40. A graph G = (V,E) satisfies | E | £ 3 | V | - 6. The min-degree of G is defined as

min {degree (v)}. Therefore, min-degree of G cannot be

v Î V

• 3
• 4
• 5
• 6

41. Consider the following system of linear equations

Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of a , does this system of equations have infinitely many solutions?

• 0
• 1
• 2
• infinitely many

42. A piecewise linear function f(x) is plotted using thick solid lines in the figure below (the plot is drawn to scale).

I f we use the Newton-Raphson method to find the roots of f(x) = 0 using x 0, x 1 and x 2 respectively as initial guesses, the roots obtained would be

(a) 1.3, 0.6, and 0.6 respectively

(b) 0.6, 0.6, and 1.3respectively

(c) 1.3, 1.3, and 0.6 respectively

(d) 1.3,0.6, and 1.3 respectively

43. The following is a scheme for floating point number representation using 16 bits.

Bit Position 15 14 … … 9 8 … … … 0

Sign Exponent Mantissa

Let s, e, and m be the numbers represented in binary in the sign, exponent, and mantissa fields respectively. Then the floating point number represented is:

What is the maximum difference between two successive real numbers representable in this system?

• 2 –40
• 2-9
• 2 22
• 2 31

44. A 1-input, 2-output synchronous sequential circuit behaves as follows:

Let Z k n k denote the number of O's and 1's respectively in initial k bits of the input

(Z k + n k = k). The circuit outputs 00 until one of the following conditions holds.

• Z k – n k = 2. In this case, the output at the k-th and all subsequent clock ticks Is 10
• N k – Z k = 2. In this case, the output at the k-th and all subsequent clock ticks is 01.

What is the minimum number of states required in the state transition graph of the above circuit? ­

• 5
• 6
• 7
• 8

45. The literal count of a boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of (xy + xz') is 4. What are the minimum possible literal counts of the product-or-sum and sum-of ­product representations respectively of the function given by the following Karnaugh map? Here, X denotes "don't care"

• (11, 9)
• (9, 13)
• (9, 10)
• (11, 11)

46. Consider the ALU shown below.

If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C o only (+ and -denote addition and subtraction respectively)?

• A+ B, and A-B, but not A+ 1
• A+B, and A+ 1, but not A-B
• A + B, but not A - B, or A + 1

(d) A+ B, and A-B, and A+ 1

47. Consider the following circuit composed of XOR gates and non-inverting buffers.

The non-inverting buffers have delays d 1 = 2 ns and d 2 = 4 ns as shown in the figure. Both XOR gates and all wires have zero delay. Assume that all gate inputs, outputs and wires are stable at logic level 0 at time 0. If the following waveform is applied at input A, how many transition(s) (change of logic levels) occur(s) at B during the interval from 0 to 10 ns ?

• 1
• 2
• 3
• 4

THE FOLLOWING INFORMATION PERTAINS TO Q. 48-49

Consider the following assembly language program for a hypothetical processor. A, B and C are 8 bit registers. The meanings of various instructions are shown as comments.

MOVB, #0 ; B ¬ O

MOVC, #8 ; C ¬ 8

Z: CMP C, # 0 ; compare C with 0

JZX ; jump to X if zero flag is set

SUB C, # 1 ; C ¬ C-l

RRCA, # 1 ; right rotate A through carry by one bit. Thus:

; if the initial values of A and the carry

flag are a 7...a O and

; Co respectively, their values after the execution

of this

; instruction will be C 0a 7...a 1 and a 0 respectively.

JCY ; jump to Y if carry flag is set

JMPZ ; jump to Z

Y: ADD B, # 1 ; B ¬ B+l

JMPZ ; jump to Z

X:

48. If the initial value of register A is A 0, the value of register B after the program execution will be

• the number of 0 bits in A 0
• the number of 1 bits in A 0
• A 0
• 8

49. Which of the following instructions when inserted at location X will ensure that the value of register A after program execution is the same as its initial value?

• RRCA, #
• NOP ; no operation
• LRC A, # 1 ; left rotate A through carry flag by one bit
• ADD A, # 1

50. Consider the following deterministic finite state automaton M.

Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

(a) 1 (b) 5

(c) 7 (d) 8

­

51. 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)

52. 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

53. 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

54. 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

55. 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

56. 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 }

57. 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)

58. 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

59. 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

60. 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

61. 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]

62. 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)

(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