Andhra University 2006 B.E Information Technology COMPUTER SCIENCE

2
30
56
256



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

(a)
3 n
(2n)!

2 n




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

Then T(n) = where x is


n - k + one
n - k
n - k – one
n - k - two



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 resulting graph must necessarily lie ranging from
k and n
k - one and k + one
k - one and n - one
k + one and n-k



9. Assuming all numbers are in 2's complement representation, which of the subsequent numbers is divisible by 11111011 ?
11100111
11100100
11010111
11011011



10. For a pipelined CPU with a single ALU, consider the subsequent situations
The j + 1-st instruction uses the outcome 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 identical time

Which of the above can reason a hazard?
I and II only
II and III only
III only
All the 3



11. Consider an array multiplier for multiplying 2 n bit numbers. If every 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 issue Õis NP-complete. Ram indicates a polynomial time reduction from the 3-SAT issue to Õ, and Shyam indicates a polynomial time reduction from Õ to 3-SAT. Which of the subsequent 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 described as follows:

Earning:   Approval pending.