GATE IT 2004

In a population of N families, 50% of the families have three children, 30% of the families have two children and the remaining families have one child. What is the probability that a randomly picked child belongs to a family with two children?

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 students have taken Computer Organization course; 50 students have taken both Programming Language and Data Structures, 35 students have taken both Programming Language and Computer Organization; 30 students have taken both Data Structures and Computer Organization, 15 students have taken all the three courses. How many students have not taken any of the three courses?

Let a(x, y), b(x, y,) and c(x, y) be three statements with variables x and y chosen from some universe. Consider the following statement:
\qquad(\exists x)(\forall y)[(a(x, y) \wedge b(x, y)) \wedge \neg c(x, y)]
Which one of the following is its equivalent?

Let R_{1} be a relation from A =\left \{ 1,3,5,7 \right \} to B = \left \{ 2,4,6,8 \right \}. R_{2} be another relation from B to C = {1, 2, 3, 4} as defined below:

i. An element x in A is related to an element y in B (under R_{1}) if x + y is divisible by 3.
ii. An element x in B is related to an element y in C (under R_{2}) if x + y is even but not divisible by 3.

Which is the composite relation R_{1}R_{2} from A to C?

What is the maximum number of edges in an acyclic undirected graph with n vertices?

What values of x, y and z satisfy the following system of linear equations?
\begin{bmatrix} 1 &2 &3 \\ 1& 3 &4 \\ 2& 2 &3 \end{bmatrix} \begin{bmatrix} x\\y \\ z \end{bmatrix} = \begin{bmatrix} 6\\8 \\ 12 \end{bmatrix}

Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c)^*?

What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function without using any other logic gate?

Which one of the following statements is FALSE?

What is the minimum size of ROM required to store the complete truth table of an 8-bit \times 8-bit multiplier?