## APPSC-2016-DL-CS

Question 1 |

The minimum number of edges of a graph containing n vertices and c connected components is

n-c | |

c | |

c(n-1) | |

n/c |

Question 1 Explanation:

We have to find a minimum no. of edges. So for c connected components let's assume c-1 independent vertices which are also c-1 components and remaining 1 component will contain n-(c-1) vertices or n-c+1 vertices. So for minimum no. of edges will be no. of vertices in the single component (which contains n-c+1 vertices) -1, which is
(n-c+1)-1 = n-c

Question 2 |

In first order predicate logic, ∼∀x P(x) is equivalent to Options:

∼∃x P(x) | |

∃x ∼P(x) | |

∀x ∼P(x) | |

the given expression is not a well formed |

Question 2 Explanation:

∼∀x P(x) = ∃x ∼P(x)

Question 3 |

How many different 6-member committees can be formed from 6 men and 4 women with a restriction that each committee should include an equal number of men and women

120 | |

80 | |

420 | |

6045 |

Question 3 Explanation:

Given data,

Committee members=6,

Mens=6

Women=4

Equal numbers of men and women are= ?

3 men out of 6, 3 women out of 4

⇒

⇒ 20 * 4

⇒ 80

Note: There are 3 possibilities to consider an equal number of men and women.

Choose 4 men and 4 women then we get

Choose 2 men and 2 women then we get

Committee members=6,

Mens=6

Women=4

Equal numbers of men and women are= ?

3 men out of 6, 3 women out of 4

⇒

^{6}C_{3}*^{4}C_{3}ways⇒ 20 * 4

⇒ 80

Note: There are 3 possibilities to consider an equal number of men and women.

Choose 4 men and 4 women then we get

^{6}C^{4}*^{4}C_{4}ways = 15Choose 2 men and 2 women then we get

^{6}C_{2}*^{4}C^{2 ways = 90 Choose 3 men and 3 women then we get 6C3 * 4C3 ways = 80}Question 4 |

Consider 4-character long codes generated by using an alphabet consisting of 8-characters with no restriction on the number of repetitions of a character in a code. How many codes at least one character repeated?

2416 | |

6720 | |

1680 | |

4096 |

Question 5 |

How many distinct Boolean functions can be formed from ‘n’ Boolean variables?

n ^{2} | |

2n ^{2} | |

2n | |

2 to the power of 2 ^{n} |

Question 5 Explanation:

Each “boolean” variable has two possible values i.e 0 and 1.

Number of variables= n

Number of input combinations is 2

Each “boolean” function has two possible outputs i.e 0 and 1.

Number of boolean functions possible is 2

Formula: The number of m-ary functions possible with n k-ary variables is m

Number of variables= n

Number of input combinations is 2

^{n}.Each “boolean” function has two possible outputs i.e 0 and 1.

Number of boolean functions possible is 2

^{2^n}.Formula: The number of m-ary functions possible with n k-ary variables is m

^{k^n}.Question 6 |

In order for a function to be invertible, it should be _______

one-one | |

onto | |

both one-one and onto | |

into |

Question 6 Explanation:

A function is invertible if and only if it is both one-one and onto.

Question 7 |

What is the maximum value of the function f(x)=x

^{2}-3x+5 in the internal [0,5]?15 | |

5 | |

3 | |

9 |

Question 7 Explanation:

Question 8 |

In an IT company, given that the probability of finding an employee with programming skills is 0.7, documentation skills is 0.6, and if the probability of finding an employee with either of the skills is 0.9, then what is the probability of finding an employee with both the skills?

0.42 | |

0.5 | |

0.4 | |

0.8 |

Question 8 Explanation:

Let A = probability of finding an employee with programming skills

Let B = probability of finding an employee with documentation skill

So A=0.7

B=0.6

AUB=0.9

Hence ,A∩B = A + B - (AUB)

= 0.7+0.6-0.9

= 0.4

Let B = probability of finding an employee with documentation skill

So A=0.7

B=0.6

AUB=0.9

Hence ,A∩B = A + B - (AUB)

= 0.7+0.6-0.9

= 0.4

Question 9 |

Let A, B and C are finite sets. Which of the following options is TRUE, if X=((A∩B)-(B∩C)) and Y=(A-(A∩C))-(A-B)?

X⊂Y | |

X⊃Y | |

X=Y | |

X-Y≠φ and Y-X≠φ |

Question 9 Explanation:

Now,

x=((AB)-(BC))

=(b,c)-(e,f))

=b

y=(A-(AC))-(A-B)

=((a,b,d,e)-(d,e))-(a,d)

=(a,b)-(a,d)

=b

Hence, x=y

Question 10 |

Which of the following options is TRUE with regard to a relation R defined on ordered pairs of integers as given below: (x,y) R (low,up) if x>low and y<up?

R is totally ordered | |

R is partially ordered but not totally ordered
| |

R is an equivalence relation | |

R is neither partially ordered nor an equivalence relation |

Question 10 Explanation:

If a relation is equivalence then it must be

i) Symmetric

ii) Reflexive

iii) Transitive

If a relation is a partial order relation then it must be

i) Reflexive

ii) Anti-symmetric

iii) Transitive

If a relation is total order relation then it must be

i) Reflexive

ii) Symmetric

iii) Transitive

iv) Comparability

Given ordered pairs are (x,y)R(low,up) if (x,up).

Here < , > are using while using these symbols between (x,y) and (y,up) then they are not satisfy the reflexive relation. If they use (x< =low) and (y >=low) then reflexive relation can satisfies.

So, given relation cannot be an Equivalence. Total order relation or partial order relation.

i) Symmetric

ii) Reflexive

iii) Transitive

If a relation is a partial order relation then it must be

i) Reflexive

ii) Anti-symmetric

iii) Transitive

If a relation is total order relation then it must be

i) Reflexive

ii) Symmetric

iii) Transitive

iv) Comparability

Given ordered pairs are (x,y)R(low,up) if (x,up).

Here < , > are using while using these symbols between (x,y) and (y,up) then they are not satisfy the reflexive relation. If they use (x< =low) and (y >=low) then reflexive relation can satisfies.

So, given relation cannot be an Equivalence. Total order relation or partial order relation.

Question 11 |

The Hasse diagram representing a lattice, P when turned upside-down represents the poset, Q. Poset Q is a ______

dual of P | |

Greatest Upper Bound of P | |

Lattice | |

dual of P and Lattice |

Question 11 Explanation:

The Hasse diagram representing a lattice, P when turned upside-down represents the poset Q which is dual of P and lattice.

Question 12 |

A pair of dice is tossed twice. What is the probability of scoring 9 at least in one of the two times?

16/81 | |

17/81 | |

1/36 | |

64/81 |

Question 12 Explanation:

We will use binomial distribution here.

Total possible outcomes will be 6*6=36

Lets first calculate probability of getting sum as 9. We will get sum as 9 when first dice and second dice will have number (3,6) ,(4,5) ,(5,4) ,(6,3). So total 4 possibility are there out of 36.

So Let probability of getting sum as 9 = P(A) = 4/36 = 1/9

Now

Probability of scoring 9 at least in one of the two times

= Probability of scoring 9 exactly one time + Probability of scoring 9 exactly two times

Total possible outcomes will be 6*6=36

Lets first calculate probability of getting sum as 9. We will get sum as 9 when first dice and second dice will have number (3,6) ,(4,5) ,(5,4) ,(6,3). So total 4 possibility are there out of 36.

So Let probability of getting sum as 9 = P(A) = 4/36 = 1/9

Now

Probability of scoring 9 at least in one of the two times

= Probability of scoring 9 exactly one time + Probability of scoring 9 exactly two times

Question 13 |

Which of the following probability distributions is applicable to consider the problem of estimating the probability of exactly two defective items manufactured in an industry in a batch of 20 items, if the probability of manufacture defect is 0.1?

Poisson distribution | |

Binomial distribution | |

Uniform distribution | |

Gaussian distribution |

Question 13 Explanation:

Binomial distribution will be used.
And will be calculated as

^{20}C_{2}= (0.1)^{2}(0.9)^{18}Question 14 |

The propositional expression [(∼P∨Q)→(Q→P)] is

a tautology | |

not a tautology | |

contradiction | |

not a well-formed formula |

Question 14 Explanation:

Question 15 |

The maximum number of non-zero elements of a n×n matrix whose [i,j]th element is equal to 0 for all i<j is

n(n-1)/2 | |

n(n+1)/2 | |

n ^{2} | |

n |

Question 15 Explanation:

From given description we can conclude that all the elements above the diagonal are 0. So we can say that,

1st row will have 1 non-zero element,

2nd row will have 2 non zero elements,

3rd row will have 3 non-zero elements ,

:

:

:

nth row will contain n non-zero elements.

Therefore total no. of non-zero elements are,

1+2+3+...........+n = n(n+1)/2

1st row will have 1 non-zero element,

2nd row will have 2 non zero elements,

3rd row will have 3 non-zero elements ,

:

:

:

nth row will contain n non-zero elements.

Therefore total no. of non-zero elements are,

1+2+3+...........+n = n(n+1)/2

Question 16 |

At a given moment a

**queue contains stored in it**. If the capacity of the queue is 6 then which of the following sequence of operations results in a modified queue contents?delete a, b; and insert e,a,f; | |

insert e,a,f and delete a,b | |

insert e, delete b and insert f
| |