250+ TOP MCQs on Inclusion-Exclusion Principle and Answers

Data Structures & Algorithms Multiple Choice Questions on “Inclusion-Exclusion Principle”.

1. Which one of the following problem types does inclusion-exclusion principle belong to?
a) Numerical problems
b) Graph problems
c) String processing problems
d) Combinatorial problems

Answer: d
Clarification: Inclusion-Exclusion principle is a kind of combinatorial problem. It is a counting technique to obtain the number of elements present in sets( two, three , etc.,).

2. Which of the following is a correct representation of inclusion exclusion principle (|A,B| represents intersection of sets A,B)?
a) |A U B|=|A|+|B|-|A,B|
b) |A,B|=|A|+|B|-|A U B|
c) |A U B|=|A|+|B|+|A,B|
d) |A,B|=|A|+|B|+|A U B|
Answer: a
Clarification: The formula for computing the union of two sets according to inclusion-exclusion principle is |A U B|=|A|+|B|-|A,B| where |A,B| represents the intersection of the sets A and B.

3. ____________ is one of the most useful principles of enumeration in combinationatorics and discrete probability.
a) Inclusion-exclusion principle
b) Quick search algorithm
c) Euclid’s algorithm
d) Set theory

Answer: a
Clarification: Inclusion-exclusion principle serves as one of the most useful principles of enumeration in combinationatorics and discrete probability because it provides simple formula for generalizing results.

4. Which of the following is not an application of inclusion-exclusion principle?
a) Counting intersections
b) Graph coloring
c) Matching of bipartite graphs
d) Maximum flow problem
View Answer

Answer: d
Clarification: Counting intersections, Graph coloring and Matching of bipartite graphs are all examples of inclusion-exclusion principle whereas maximum flow problem is solved using Ford-Fulkerson algorithm.

5. Who invented the concept of inclusion-exclusion principle?
a) Abraham de Moivre
b) Daniel Silva
c) J.J. Sylvester
d) Sieve
Answer: a
Clarification: The concept of inclusion- exclusion principle was initially invented by Abraham de Moivre in 1718 but it was published first by Daniel Silva in his paper in 1854.

6. According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is even.
a) True
b) False

Answer: b
Clarification: According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is odd and excluded if n is even.

7. With reference to the given Venn diagram, what is the formula for computing |AUBUC| (where |x, y| represents intersection of sets x and y)?
inclusion-exclusion-principle-questions-answers-q7
a) |A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C|
b) |A, B,C|=|A|+|B|+|C|-|A U B|-|A U C|-|B U C|+|A U B U C|
c) |A, B,C|=|A|+|B|+|C|+|A,B|-|A,C|+|B,C|+|A U B U C|
d) |A U B U C|=|A|+|B|+|C| + |A,B| + |A,C| + |B,C|+|A, B,C|

Answer: a
Clarification: The formula for computing the union of three sets using inclusion-exclusion principle is|A U B U C|=|A|+|B|+|C|-|A,B|-|A,C|-|B,C|+|A, B,C| where |A,B|, |B,C|, |A,C|, |A,B,C| represents the intersection of the sets A and B, B and C, A and C, A, B and C respectively.

8. Which of the following statement is incorrect with respect to generalizing the solution using the inclusion-exclusion principle?
a) including cardinalities of sets
b) excluding cardinalities of pairwise intersections
c) excluding cardinalities of triple-wise intersections
d) excluding cardinalities of quadraple-wise intersections
Answer: c
Clarification: According to inclusion-exclusion principle, an intersection is included if the intersecting elements are odd and excluded, if the intersecting elements are even. Hence triple-wise intersections should be included.

9. Counting intersections can be done using the inclusion-exclusion principle only if it is combined with De Morgan’s laws of complementing.
a) true
b) false

Answer: a
Clarification: The application of counting intersections can be fulfiled if and only if it is combined with De Morgan laws to count the cardinality of intersection of sets.

10. Using the inclusion-exclusion principle, find the number of integers from a set of 1-100 that are not divisible by 2, 3 and 5.
a) 22
b) 25
c) 26
d) 33

Answer: c
Clarification: Consider sample space S={1,…100}. Consider three subsets A, B, C that have elements that are divisible by 2, 3, 5 respectively. Find integers that are divisible by A and B, B and C, A and C. Then find the integers that are divisible by A, B, C. Applying the inclusion-exclusion principle, 100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.

11. ____________ is an arithmetic function that calculates the total number of positive integers less than or equal to some number n, that are relatively prime to n.
a) Euler’s phi function
b) Euler’s omega function
c) Cauchy’s totient function
d) Legrange’s function
Answer: a
Clarification: Euler’s phi function is an arithmetic function that calculates the total number of positive integers less than or equal to some number n, that are relatively prime to n. The inclusion-exclusion principle is used to obtain a formula for Euler’s phi function.

12. Let A={1,2,3} B={2,3,4} C={1,3,5} D={2,3}. Find the cardinality of sum of all the sets.
a) 6
b) 5
c) 4
d) 7

Answer: b
Clarification: First, include the cardinalities of all the sets. Then, exclude the cardinalities of even intersections. Then include the cardinalities of odd intersections. Hence, 3+3+3+2-2-2-2-1-2-1+1+2+1+1-1=5.

and Answers.

contest

Leave a Reply

Your email address will not be published. Required fields are marked *