Solution Found!
a) Suppose we have n subsets S1. S2,…, Sn of the set {1,
Chapter 3, Problem 11E(choose chapter or problem)
a) Suppose we have n subsets S1. S2,…, Sn of the set {1, 2, …, n}. Express a brute-force algorithm that determines whether there is a disjoint pair of these subsets. [Hint: The algorithm should loop through the subsets: for each subset Si, it should then loop through all other subsets: and for each of these other subsets Sj, it should loop through all elements k in Si, to determine whether k also belongs to Sj.]________________b) Give a big-O estimate for the number of times the algorithm needs to determine whether an integer is in one of the subsets.
Questions & Answers
QUESTION:
a) Suppose we have n subsets S1. S2,…, Sn of the set {1, 2, …, n}. Express a brute-force algorithm that determines whether there is a disjoint pair of these subsets. [Hint: The algorithm should loop through the subsets: for each subset Si, it should then loop through all other subsets: and for each of these other subsets Sj, it should loop through all elements k in Si, to determine whether k also belongs to Sj.]________________b) Give a big-O estimate for the number of times the algorithm needs to determine whether an integer is in one of the subsets.
ANSWER:Solution:Step 1In this problem we need to write an algorithm which finds whether there is a disjoint pair of subsets in n subsets of {1, 2, …, n}. We are also asked to find the big-O estimate for the number of times the algorithm computes if an integer is in one of the subsets.