This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer
Explanation: 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|
View Answer
Explanation: 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
View Answer
Explanation: 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
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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)?
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|
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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
View Answer
Explanation: 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.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Check Computer Science Books
- Apply for Computer Science Internship
- Check Programming Books
- Practice Computer Science MCQs
- Practice Programming MCQs
