Data Structures & Algorithms Multiple Choice Questions on “Inclusion-Exclusion Principle”.
1. Which one of the following problem types does inclusion-exclusion principle belong to? Answer: d 2. Which of the following is a correct representation of inclusion exclusion principle (|A,B| represents intersection of sets A,B)? 3. ____________ is one of the most useful principles of enumeration in combinationatorics and discrete probability. Answer: a 4. Which of the following is not an application of inclusion-exclusion principle? Answer: d 5. Who invented the concept of inclusion-exclusion principle? 6. According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is even. Answer: b 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)? Answer: a 8. Which of the following statement is incorrect with respect to generalizing the solution using the inclusion-exclusion principle? 9. Counting intersections can be done using the inclusion-exclusion principle only if it is combined with De Morgan’s laws of complementing. Answer: a 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. Answer: c 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. 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. Answer: b
a) Numerical problems
b) Graph problems
c) String processing problems
d) Combinatorial problems
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.,).
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.
a) Inclusion-exclusion principle
b) Quick search algorithm
c) Euclid’s algorithm
d) Set theory
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.
a) Counting intersections
b) Graph coloring
c) Matching of bipartite graphs
d) Maximum flow problem
View Answer
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.
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.
a) True
b) False
Clarification: According to inclusion-exclusion principle, a n-tuple wise intersection is included if n is odd and excluded if n is even.
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|
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.
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.
a) true
b) false
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.
a) 22
b) 25
c) 26
d) 33
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.
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.
a) 6
b) 5
c) 4
d) 7
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.