**Engineering-Mathematics |Gate-2008|**

- If P, Q, R are subsets of the universal set U, then (P∩Q∩R) ∪ (P
^{c}∩Q∩R) ∪ Q^{c }∪ R^{c}is :**[GATE – 2008]**

a. Q^{c} ∪ R^{c}

b. P ∪ Q^{c} ∪ R^{c}

c. P^{c} ∪ Q^{c} ∪ R^{c}

d. U

*Answer : d)*

- The following system of equations x1 + x2 + 2×3 = 1 x1 + 2×2 + 3 x3 = 2 x1 + 4×2 + ax3 = 4 has a unique solution. The only possible value(s) for a is/are :
**[GATE – 2008]**

a. 0

b. either 0 or 1

c. any real number

d. one of 0, 1 or -1

*Answer: c)*

- The Newton-Raphson iteration

can be used to compute the : **[GATE – 2008]**

a. square of R

b. reciprocal of R

c. square root of R

d. logarithm of R

*Answer : c)*

- Which of the following statements is true for every planar graph on n vertices?
**[GATE – 2008]**

a. The graph has a vertex-cover of size at most 3n/4

b. The graph is Eulerian

c. The graph is connected

d. The graph has an independent set of size at least n/3

*Answer : a)*

- A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x
^{4}– 16x^{3}+ 24x^{2}+ 37 is :**[GATE – 2008]**

a. 0

b. 1

c. 2

d. 3

*Answer : b)*

- Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?
**[GATE – 2008]**

a. 0.24

b. 0.4

c. 0.36

d. 0.6

*Answer : b)*

- Let X be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean -1 and variance unknown. If P(X ≤ -1) = P(Y ≥ 2), the standard deviation of Y is :
**[GATE – 2008]**

a. 3

b. 2

c. 1

d. √2

*Answer : a)*

- Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following: Each finite state automaton has an equivalent pushdown automaton :
**[GATE – 2008]**

a. (∀x fsa(x)) ⇒ (∃y pda(y) ∧ equivalent(x,y))

b. ∼∀y(∃x fsa(x) ⇒ pda(y) ∧ equivalent(x,y))

c. ∀x ∃y(fsa(x) ∧ pda(y) ∧ equivalent(x,y))

d. ∀x ∃y(fsa(y)∧ pda(x) ∧ equivalent(x,y))

*Answer : a)*

- P and Q are two propositions. Which of the following logical expressions are equivalent?
**[GATE – 2008]**

a. Only I and II

b. Only I ,III and II

c. Only I, II and IV

d. All of I, II, III and IV

*Answer : b)*

- A sample space has two events A and B such that probabilities P(A ∩ B) = 1/2, P(A’) = 1/3, P(B’) = 1/3. What is P(A ∪ B)?
**[GATE – 2008]**

a. 11/12

b. 10/12

c. 9/12

d. 8/12

*Answer : b)*

- What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
**[GATE – 2008]**

a. 5

b. 4

c. 3

d. 2

*Answer : c)*

- Which of the following first order formula is logically valid? Here α(x) is a first order formula with x as a free variable, and β is a first order formula with no free variable.
**[GATE – 2008]**

a. [β→(∃x,α(x))]→[∀x,β→α(x)]

b. [(∃x,α(x))→β]→[∀x,α(x)→β]

c. [∃x,β→α(x)]→[β→(∀x,α(x))]

d. [(∀x,α(x))→β]→[∀x,α(x)→β]

*Answer : b)*

- Which of the following is the negation of [∀ x, α → (∃y, β → (∀ u, ∃v, y))]
**[GATE – 2008]**

a. [∃ x, α → (∀y, β → (∃u, ∀ v, y))]

b. [∃ x, α → (∀y, β → (∃u, ∀ v, ¬y))]

c. [∀ x, ¬α → (∃y, ¬β → (∀u, ∃ v, ¬y))]

d. [∃ x, α ʌ (∀y, β ʌ (∃u, ∀ v, ¬y))]

*Answer : d)*

- The exponent of 11 in the prime factorization of 300! Is :
**[GATE – 2008]**

a. 27

b. 28

c. 29

d. 30

*Answer : c)*

- What is the chromatic number of the following graph?
**[GATE – 2008]**

a. 2

b. 3

c. 4

d. 5

*Answer : b)*

- Consider the field C of complex numbers with addition and multiplication. Which of the following form(s) a subfield of C with addition and multiplication? (S1) the set of real numbers (S2) {(a + ib) | a and b are rational numbers} (S3) {a + ib | (a
^{2}+ b^{2}) ≤ 1} (S4) {ia | a is real}**[GATE – 2008]**

a. Only S1

b. S1 and S3

c. S2 and S3

d. S1 and S2

*Answer : d)*

- G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be :
**[GATE – 2008]**

a. Regular

b. Complete

c. Hamilton

d. Euler

*Answer : d)*

Engineering-Mathematics |Gate-2008|

- If M is a square matrix with a zero determinant, which of the following assertion (s) is (are) correct? (S1) Each row of M can be represented as a linear combination of the other rows (S2) Each column of M can be represented as a linear combination of the other columns (S3) MX = 0 has a nontrivial solution (S4) M has an inverse :
**[GATE – 2008]**

a. S3 and S2

b. S1 and S4

c. S1 and S3

d. S1, S2 and S3

*Answer : d)*

Engineering-Mathematics |Gate-2008|

- Consider the function f(x) = x
^{2}– 2x – 1. Suppose an execution of the Newton- Raphson method to find a zero of f(x) starts with an approximation x_{0}= 2 0f x. What is the value of x_{2}, ‘the approximation of x’ that the algorithm produces after two iterations, rounded to three decimal places?**[GATE – 2008]**

a. 2.417

b. 2.419

c. 2.432

d. 2.425

*Answer : b)*

Engineering-Mathematics |Gate-2008|