**Engineering-Mathematics |Gate-2007|**

1. Consider the following two statements about the function f(x)=|x|

**P.** f(x) is continuous for all real values of x**Q.** f(x) is differentiable for all real values of x

Which of the following is TRUE? **[GATE – 2007]**

a. P is true and Q is false

b. P is false and Q is true.

c. Both P and Q are true

d. Both P and Q are false.

*Answer : a)*

2. Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are: **[GATE – 2007]**

a. n and n

b. n^{2} and n

c. n^{2} and 0

d. n and 1

*Answer : b)*

3. Let G be the non-planar graph with the minimum possible number of edges. Then G has : **[GATE – 2007]**

a. 9 edges and 5 vertices

b. 9 edges and 6 vertices

c. 10 edges and 5 vertices

d. 10 edges and 6 vertices

*Answer : c)*

4. How many different non-isomorphic Abelian groups of order 4 are there? **[GATE – 2007]**

a. 5

b. 4

c. 3

d. 2

*Answer: d)*

5. Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”? **[GATE – 2007]**

a. ¬∀x (Graph (x) ⇒ Connected (x))

b. ¬∃x (Graph (x) ∧ ¬Connected (x))

c. ¬∀x (¬Graph (x) ∨ Connected (x))

d. ∀x (Graph (x) ⇒ ¬Connected (x))

*Answer : d)*

6. Which of the following graphs has an Eulerian circuit? **[GATE – 2007]**

a. Any k-regular graph where k is an even number.

b. A complete graph on 90 vertices.

c. The complement of a cycle on 25 vertices.

d. None of the above

*Answer : c)*

7. Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1, 2, 3,….., 20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation? **[GATE – 2007]**

a. 1/2

b. 1/10

c. 9!/20!

d. None of these

*Answer : b)*

8. Let A be a 4 x 4 matrix with eigenvalues -5, -2, 1, 4. Which of the following is an eigenvalue of

[A I]

[I A]

where I is the 4 x 4 identity matrix? **[GATE – 2007]**

a. 2

b. -7

c. -5

d. 1

*Answer : a)*

9. Consider the set of (column) vectors defined bu

Which of the following is true? **[GATE – 2007]**

a. {[1,-1,0]^{T}, [1,0,-1]^{T}} is a basis for the subspace X.

b. {[1,-1,0]^{T}, [1,0,-1]^{T}} is a linearly independent set, but it does not span X and therefore is not a basis of X.

c. X is not a subspace of R^{3}

d. None of the above

*Answer : a)*

10. Consider the data given in above question. Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)? **[GATE – 2007]**

a. (20)

(10)

b. 2^{20}

c. 2^{10}

d. None of the above

*Answer : a)*

11. Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives heads with probability 1/4. One of the two coins is picked up at random with equal probability and tossed. What is the probability of obtaining heads ? **[GATE – 2007]**

a. 7/8

b. 1/2

c. 7/16

d. 5/32

*Answer : c)*

12. The minimum positive integer p such that 3^{p} modulo 17 = 1 is : **[GATE – 2007]**

a. 5

b. 8

c. 12

d. 16

*Answer : d)*

13. Which one of these first-order logic formula is valid? **[GATE – 2007]**

a. ∀x(P(x) ⇒ Q(x)) ⇒ (∀xP(x) ⇒ ∀xQ(x))

b. ∃x(P(x) ∨ Q(x)) ⇒ (∃xP(x) ⇒ ∃xQ(x))

c. ∃x(P(x) ∧ Q(x)) (∃xP(x) ∧ ∃xQ(x))

d. ∀x∃y P(x, y) ⇒ ∃y∀x P(x, y)

*Answer : a)*

14. A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division. i. (0, 0) ∊ P. ii. (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P. Consider the following ordered pairs: i. (101, 22) ii. (22, 101) iii. (145, 265) iv. (0, 153) Which of these ordered pairs of natural numbers are contained in P? **[GATE – 2007]**

a. i and iii

b. ii and iv

c. i and iv

d. iii and iv

*Answer : d)*

15. Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5. : **[GATE – 2007]**

a. 5

b. 6

c. 7

d. 10

*Answer : d)*

Engineering-Mathematics |Gate-2007|

16. In a multi-user operating system on an average, 20 requests are made to use a particular resource per hour. The arrival of requests follows a Poisson distribution. The probability that either one, three or five requests are made in 45 minutes is given by : **[GATE – 2007]**

a. 6.9 × 10^{6} × e^{-20}

b. 1.02 × 10^{6} × e^{-20}

c. 6.9 × 10^{3} × e^{-20}

d. 1.02 × 10^{3} × e^{-20}

*Answer : b)*

17. Let P_{1}, P_{2},….. , P_{n} be n points in the xy-plane such that no three of them are collinear. For every pair of points P_{i} and P_{j}, let L_{ij} be the line passing through them. Let Lab be the line with the steepest gradient amongst all n(n -1)/2 lines. Which one of the following properties should necessarily be satisfied ? **[GATE – 2007]**

a. P_{a} and P_{b} are adjacent to each other with respect to their x-coordinate

b. Either P_{a} or P_{b} has the largest or the smallest y-coordinate among all the points

c. The difference between x-coordinates P_{a} and P_{b} is minimum

d. None of the above

*Answer : a)*

Engineering-Mathematics |Gate-2007|

18. Let P_{1},P_{2},…,P_{n} be n points in the xy-plane such that no three of them are collinear. For every pair of points P_{i} and P_{j}, let L_{ij} be the line passing through them. Let Lab be the line with the steepest gradient among all n(n−1)/2 lines. The time complexity of the best algorithm for finding P_{a} and P_{b} is : **[GATE – 2007]**

a. Θ(n)

b. Θ(nlogn)

c. Θ(nlog^{2}n

d. Θ(n^{2})

*Answer : b)*

Engineering-Mathematics |Gate-2007|