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