Question

Discrete Math

True or false, justify your answer. 1. If A and B are finite collections then |A UBI = |A+ B]. 2. Counting principles may be applied when analyzing the complexity of an algorithm. 3. Let TI and T2 be independent tasks, if T1 can be performed in nl ways and T2 can be completed in n2 ways, then T1 followed by T2 can be realized in n1.n2 ways. 4. For osks, cik, n) · Pſk, k) = Pik, n).

Answer 1

Solution:-

1) Correct answer - False

If A and B are two finite collection then
|A U B| = |A| + |B| - |A B|. So the given statement is false.

2) Correct answer - True

Counting principles may be used while analysis of the complexity of algorithm as in the case of linear search algorithm where you need to find the element is in the list or not then every element is compared with the search element so for n elements n comparison are made and time complexity is big-Oh(n).

3) Correct answer - False

Since both the tasks are independent so the number of ways of performing them is alsi independent. Therefore by the fundamental principle of addition T1 followed by T2 can be realised in n1 + n2 ways.

4) Correct answer - True

LHS = C(k,n) . P(k,k)
LHS = C(k,n) . C(k,k) . k!
LHS = C(k,n) . 1 . k!
LHS = C(k,n) . k!
LHS = P(k,n)
RHS = P(k,n)
Therefore, LHS = RHS.