### SET 5

Question 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?

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 Discuss it!

.

Correct answer is :A

Question 2

**Let S be a set of nelements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:**

A : n and n

B : n^{2} and n

C : n^{2} and 0

D : n and 1

Answer Discuss it!

.

Correct answer is :B

Question 3

**Let G be the non-planar graph with the minimum possible number of edges. Then G has**

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 Discuss it!

.

Correct answer is :B

Solution :

For a simple, connected, planar graph with v vertices and e edges, the following simple conditions hold: If v ? 3 then e ? 3v ? 6;

Question 4

**How many different non-isomorphic Abelian groups of order 4 are there**

A : 2

B : 3

C : 4

D : 5

Answer Discuss it!

.

Correct answer is :B

Question 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”?

A : A

B : B

C : C

D : D

Answer Discuss it!

.

Correct answer is :D

Solution :

We need to find out first order logic sentence that DOES NOT
represent the statement:

“Not every graph is connected”

Option B says 'There exist some x such that x is a graph AND
not connected'

So B is right option.

Option A and option C are same G(x)-->C(x) can also be written
as ~G(x) or C(x), and they are the correct representation.

Option C says: There exists a graph and graph is not connected,
which is equivalent to given sentence.

Option D: Every x which

Question 6

**Which of the following graphs has an Eulerian circuit?**

A : Any k-regular graph where kis 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 Discuss it!

.

Correct answer is :C

Solution :

A graph has Eulerian Circuit if following conditions are true.

a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges). ….b) All vertices have even degree. Let us analyze all options. A) Any k-regular graph where k is an even number. is not Eulerian as a k regular graph may not be connected (property b is true, but a may not) B) A complete graph on 90 vertices is not Eulerian because all vertices have degree as 89 (property b is false) C) The complement of a cycle on 25 vertices is Eulerian. In a cycle of 25 vertices, all vertices have degree as 2. In complement graph, all vertices would have degree as 22 and graph would be connected.

Question 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?**

A : 1/2

B : 1/10

C : 9!/10!

D : None of the above

Answer Discuss it!

.

Correct answer is :D

Question 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?

A : -5

B : -7

C : 2

D : 1

Answer Discuss it!

.

Correct answer is :C

Question 9

A : A

B : B

C : C

D : D

Answer Discuss it!

.

Correct answer is :C

Question 10

**Consider the set of (column) vectors defined by**

X = { x ∈ R^{3} | x1+x2+x3=0 , where x^{T} = [x1,x2,x3]^{T} .of the following is TRUE?

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

C : X is not a subspace of R^{3}

D : None of the above

Answer Discuss it!

.

Correct answer is :B

Question 11

**Consider the series X**^{n+1} = X^{n} / 2 + 98 X^{n}, X^{0} = 0.5 obtained from the Newton-Raphson method. The series converges to

A : 1.5

B : √2

C : 1.6

D : 1.4

Answer Discuss it!

.

Correct answer is :A

Question 12

**Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?**

A : There is a minimum spanning tree containing e.

B : If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have

C : Every minimum spanning tree has an edge of weight w

D : e is present in every minimum spanning tree

Answer Discuss it!

.

Correct answer is :D

Solution :

(A), (B) and (C) are correct.

(D) is incorrect as there may be many edges of wight w in the graph and e may not be picked up in some of the minimum spanning trees.

Question 13

**Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0, 0) **

A : 20C10

B : 2^{20}

C : 2^{10}

D : None of the above

Answer Discuss it!

.

Correct answer is :A

Question 14

**Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).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)?**

A : 2^{9}

B : 2^{19}

C : 8C4 * 11C4

D : 20C10 - (8C4 * 11C5)

Answer Discuss it!

.

Correct answer is :D

Question 15

**Evaluate the following**

A : 1

B : -1

C : INF

D : -INF

Answer Discuss it!

.

Correct answer is :A

Question 16

**The following system of equations has a unique solution. The only possible value(s) for α is/are **

A : 0

B : Either 0 or 1

C : any real number

D : any real number other than 5

Answer Discuss it!

.

Correct answer is :D

Solution :

Augment the given matrix as

1 1 2 | 1

1 2 3 | 2

1 4 a | 4

Apply R2 <- R2 - R1 and R3 <- R3 - R1

1 1 2 | 1

0 1 1 | 1

0 3 a-2 | 3

Apply R3 <- R3 - 3R2

1 1 2 | 1

0 1 1 | 1

0 0 a-5 | 0

So for the system of equations to have a unique solution,

a - 5 != 0

or

a != 5

or

a = R - {5}

Question 17

**The minimum number of equal length subintervals needed to approximate to an accuracy of at least 1/3 * 10**^{-6} using the trapezoidal rule is

A : 1000e

B : 1000

C : 100e

D : 100

Answer Discuss it!

.

Correct answer is :A

Question 18

**The Newton-Raphson iteration x**_{n+1} = 1/2(x_{n} + R/x_{n}) can be used to compute the.

A : square of R

B : reciprocal of R

C : square root of R

D : logarithm of R

Answer Discuss it!

.

Correct answer is :C

Solution :

According to Newton-Raphson method,

x_{n+1} = x_{n} - f(x_{n}) / f`(x_{n})

So we try to bring given equation in above form. Given equation is :

x_{n+1} = x_{n}/2 + R/(2x_{n})

= x_{n} - x_{n}/2 + R/(2x_{n})

= x_{n} - (x_{n}^{2} - R2)/(2x_{n})

So clearly f(x) = x2 - R, so root of f(x) means x2 - R = 0 i.e. we are trying to find square root of R. So option (C) is corr

Question 19

A : P=Q-k

B : P=Q+k

C : P=Q

D : P=Q+2k

Answer Discuss it!

.

Correct answer is :A

Question 20

**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

A : 0

B : 1

C : 2

D : 3

Answer Discuss it!

.

Correct answer is :B

Solution :

f(x)=3x^{4} - 16x^{3} + 24x^{2} + 37

f`(x)=12x^{3} - 48x^{2} + 48x

f``(x)= 36x^{2} - 96x + 48

f`(x) = 0 => 12x (x^{2} - 4x + 4) = 12x (x-2)^{2}

f`(x) is negative for all x< 0 and positive for all x > 0

=> f(x) is decreasing to the left of zero and increasing to the right of zero

=> f(x) has only one minimum (extrema) at x = 0

Question 21

**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?**

A : 0.24

B : 0.36

C : 0.4

D : 0.6

Answer Discuss it!

.

Correct answer is :C

Question 22

**How many of the following matrices have an eigenvalue 1?**

A : 1

B : 2

C : 3

D : 4

Answer Discuss it!

.

Correct answer is :A

Question 23

**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**

A : 3

B : 2

C : sqrt(2)

D : 1

Answer Discuss it!

.

Correct answer is :A

Solution :

X(1,4), Y(-1,Δ)

P(X <= -1)Z = -1-1/2 = -1

=P(Z <= -1)= P(Z >= 1) = 0.5 - P(0 < Z < 1)

=0.5 - 0.3413 = 0.1587

if Δ = 3,then P(Z >= 2),Z = 2+1/3 = 1

=P(Z >= 1) = 0.1587

Question 24

**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.**

A : A

B : B

C : C

D : D

Answer Discuss it!

.

Correct answer is :A

Question 25

**P and Q are two propositions. Which of the following logical expressions are equivalent?**

I. P ∨ ~Q

II. ~(~P ∧ Q)

III. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ ~Q)

IV.(P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ Q)

A : Only I and II

B : Only I,II and III

C : Only I,II and IV

D : All of I,II,III and IV

Answer Discuss it!

.

Correct answer is :B

Solution :

I and II are same by Demorgan's law The IIIrd can be simplified to P ∨ ~P is always true.

Question 26

**G is a graph on n vertices and 2n - 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?**

A : For every subset of k vertices, the induced subgraph has at most 2k-2 edges

B : The minimum cut in G has at least two edges

C : There are two edge-disjoint paths between every pair to vertices

D : There are two vertex-disjoint paths between every pair of vertices

Answer Discuss it!

.

Correct answer is :D

Solution :

Counter for option D is as follows. Take two copies of K4(complete graph on 4 vertices), G1 and G2. Let V(G1)={1,2,3,4} and V(G2)={5,6,7,8}. Construct a new graph G3 by using these two graphs G1 and G2 by merging at a vertex, say merge (4,5). The resultant graph is two edge connected, and of minimum degree 2 but there exist a cut vertex, the merged vertex.

Question 1

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?

.

Correct answer is :A

Question 2

.

Correct answer is :B

Question 3

.

Correct answer is :B

Solution :

For a simple, connected, planar graph with v vertices and e edges, the following simple conditions hold: If v ? 3 then e ? 3v ? 6;

Question 4

.

Correct answer is :B

Question 5

“Not every graph is connected”?

.

Correct answer is :D

Solution :

We need to find out first order logic sentence that DOES NOT represent the statement:

“Not every graph is connected”

Option B says 'There exist some x such that x is a graph AND not connected'

So B is right option.

Option A and option C are same G(x)-->C(x) can also be written as ~G(x) or C(x), and they are the correct representation.

Option C says: There exists a graph and graph is not connected, which is equivalent to given sentence.

Option D: Every x which

Question 6

.

Correct answer is :C

Solution :

A graph has Eulerian Circuit if following conditions are true.

a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges). ….b) All vertices have even degree. Let us analyze all options. A) Any k-regular graph where k is an even number. is not Eulerian as a k regular graph may not be connected (property b is true, but a may not) B) A complete graph on 90 vertices is not Eulerian because all vertices have degree as 89 (property b is false) C) The complement of a cycle on 25 vertices is Eulerian. In a cycle of 25 vertices, all vertices have degree as 2. In complement graph, all vertices would have degree as 22 and graph would be connected.

Question 7

.

Correct answer is :D

Question 8

[A I]

[I A]

where I is the 4 x 4 identity matrix?

.

Correct answer is :C

Question 9

.

Correct answer is :C

Question 10

X = { x ∈ R

^{3}| x1+x2+x3=0 , where x

^{T}= [x1,x2,x3]

^{T}.of the following is TRUE?

.

Correct answer is :B

Question 11

^{n+1}= X

^{n}/ 2 + 98 X

^{n}, X

^{0}= 0.5 obtained from the Newton-Raphson method. The series converges to

.

Correct answer is :A

Question 12

.

Correct answer is :D

Solution :

(A), (B) and (C) are correct.

(D) is incorrect as there may be many edges of wight w in the graph and e may not be picked up in some of the minimum spanning trees.

Question 13

.

Correct answer is :A

Question 14

.

Correct answer is :D

Question 15

.

Correct answer is :A

Question 16

.

Correct answer is :D

Solution :

Augment the given matrix as

1 1 2 | 1

1 2 3 | 2

1 4 a | 4

Apply R2 <- R2 - R1 and R3 <- R3 - R1

1 1 2 | 1

0 1 1 | 1

0 3 a-2 | 3

Apply R3 <- R3 - 3R2

1 1 2 | 1

0 1 1 | 1

0 0 a-5 | 0

So for the system of equations to have a unique solution,

a - 5 != 0

or

a != 5

or

a = R - {5}

Question 17

^{-6}using the trapezoidal rule is

.

Correct answer is :A

Question 18

_{n+1}= 1/2(x

_{n}+ R/x

_{n}) can be used to compute the.

.

Correct answer is :C

Solution :

According to Newton-Raphson method,

x

_{n+1}= x

_{n}- f(x

_{n}) / f`(x

_{n})

So we try to bring given equation in above form. Given equation is :

x

_{n+1}= x

_{n}/2 + R/(2x

_{n})

= x

_{n}- x

_{n}/2 + R/(2x

_{n})

= x

_{n}- (x

_{n}

^{2}- R2)/(2x

_{n})

So clearly f(x) = x2 - R, so root of f(x) means x2 - R = 0 i.e. we are trying to find square root of R. So option (C) is corr

Question 19

.

Correct answer is :A

Question 20

^{4}- 16x

^{3}+ 24x

^{2}+ 37

.

Correct answer is :B

Solution :

f(x)=3x

^{4}- 16x

^{3}+ 24x

^{2}+ 37

f`(x)=12x

^{3}- 48x

^{2}+ 48x

f``(x)= 36x

^{2}- 96x + 48

f`(x) = 0 => 12x (x

^{2}- 4x + 4) = 12x (x-2)

^{2}

f`(x) is negative for all x< 0 and positive for all x > 0

=> f(x) is decreasing to the left of zero and increasing to the right of zero

=> f(x) has only one minimum (extrema) at x = 0

Question 21

.

Correct answer is :C

Question 22

.

Correct answer is :A

Question 23

.

Correct answer is :A

Solution :

X(1,4), Y(-1,Δ

P(X <= -1)Z = -1-1/2 = -1

=P(Z <= -1)= P(Z >= 1) = 0.5 - P(0 < Z < 1)

=0.5 - 0.3413 = 0.1587

if Δ = 3,then P(Z >= 2),Z = 2+1/3 = 1

=P(Z >= 1) = 0.1587

Question 24

.

Correct answer is :A

Question 25

I. P ∨ ~Q

II. ~(~P ∧ Q)

III. (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ ~Q)

IV.(P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ Q)

.

Correct answer is :B

Solution :

I and II are same by Demorgan's law The IIIrd can be simplified to P ∨ ~P is always true.

Question 26

.

Correct answer is :D

Solution :

Counter for option D is as follows. Take two copies of K4(complete graph on 4 vertices), G1 and G2. Let V(G1)={1,2,3,4} and V(G2)={5,6,7,8}. Construct a new graph G3 by using these two graphs G1 and G2 by merging at a vertex, say merge (4,5). The resultant graph is two edge connected, and of minimum degree 2 but there exist a cut vertex, the merged vertex.