Question 1 |

Choose the correct alternatives (More than one may be correct).

Two NAND gates having open collector outputs are tied together as shown in below figure.

The logic function Y, implemented by the circuit is,

Two NAND gates having open collector outputs are tied together as shown in below figure.

The logic function Y, implemented by the circuit is,

Y=ABC + DE | |

Y=\overline{ABC + DE} | |

Y=ABC.DE | |

Y=\overline{ABC.DE} |

Question 1 Explanation:

Question 2 |

Choose the correct alternatives (More than one may be correct).

Indicate which of the following statements are true:

A relational database which is in 3NF may still have undesirable data redundancy because there may exist:

Indicate which of the following statements are true:

A relational database which is in 3NF may still have undesirable data redundancy because there may exist:

Transitive functional dependencies | |

Non-trivial functional dependencies involving prime attributes on the right-side. | |

Non-trivial functional dependencies involving prime attributes only on the left-side. | |

Non-trivial functional dependencies involving only prime attributes. |

Question 2 Explanation:

Question 3 |

Choose the correct alternatives (More than one may be correct).

The number of rooted binary trees with n nodes is,

The number of rooted binary trees with n nodes is,

Equal to the number of ways of multiplying (n+1) matrices. | |

Equal to the number of ways of arranging n out of 2 n distinct elements. | |

Equal to \frac{1}{(n+1)}\binom{2n}{n}. | |

Equal to n!. |

Question 3 Explanation:

Question 4 |

Choose the correct alternatives (More than one may be correct).

The total external path length, EPL, of a binary tree with n external nodes is, \Sigma _w=Iw, where I_{w} is the path length of external node w),

The total external path length, EPL, of a binary tree with n external nodes is, \Sigma _w=Iw, where I_{w} is the path length of external node w),

\leq n^{2} always. | |

\geq n \log_{2} n always. | |

Equal to n^{2} always. | |

O(n) for some special trees. |

Question 4 Explanation:

Question 5 |

Choose the correct alternatives (More than one may be correct).

The complexity of comparision based sorting algorithms is:

The complexity of comparision based sorting algorithms is:

\Theta (n \log n) | |

\Theta (n) | |

\Theta \left(n^2\right) | |

\Theta (n\sqrt n) |

Question 5 Explanation:

Question 6 |

Choose the correct alternatives (More than one may be correct).

Recursive languages are:

Recursive languages are:

A proper superset of context free languages. | |

Always recognizable by pushdown automata. | |

Also called type 0 languages. | |

Recognizable by Turing machines. |

Question 6 Explanation:

Question 7 |

Choose the correct alternatives (More than one may be correct).

It is undecidable whether:

It is undecidable whether:

An arbitrary Turing machine halts after 100 steps. | |

A Turing machine prints a specific letter. | |

A Turing machine computes the products of two numbers | |

None of the above. |

Question 7 Explanation:

Question 8 |

Choose the correct alternatives (More than one may be correct).

Let R_{1} and R_{1} be regular sets defined over the alphabet \Sigma Then:

Let R_{1} and R_{1} be regular sets defined over the alphabet \Sigma Then:

R_{1} \cap R_{2} is not regular. | |

R_{1} \cup R_{2} is regular. | |

\Sigma^{*}-R_{1} is regular. | |

R_{1}^{*} is not regular. |

Question 8 Explanation:

Question 9 |

Choose the correct alternatives (More than one may be correct).

The number of ways in which 5 A's, 5 B's and 5 C's can be arranged in a row is:

The number of ways in which 5 A's, 5 B's and 5 C's can be arranged in a row is:

15!/(5!)^{3} | |

15! | |

\left(\frac{15}{5}\right) | |

15!(5!3!). |

Question 9 Explanation:

Question 10 |

Choose the correct alternatives (More than one may be correct).

Indicate which of the following well-formed formulae are valid:

Indicate which of the following well-formed formulae are valid:

\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right) | |

\left(P\Rightarrow Q\right) \Rightarrow \left( \neg P \Rightarrow \neg Q\right) | |

\left(P{\wedge} \left(\neg P \vee \neg Q\right)\right) \Rightarrow Q | |

\left(P \Rightarrow R\right) \vee \left(Q \Rightarrow R\right) \Rightarrow \left(\left(P \vee Q \right) \Rightarrow R\right) |

Question 10 Explanation:

There are 10 questions to complete.