Questions and Answers
Q: Instead of implementing set_is_subset as shown, how could we use other set operations to determine if one set, S1 , is a subset of another set, S2 ? Why is set_is_subset provided?
A: In set notation, if S 1 ∩ S 2 = S 1, then S 1 ⊂ S 2. Therefore, we could use a combination of the set_intersection and set_is_equal operations . Whether we implement this operation as shown or use set_intersection and set_is_equal, its runtime complexity is O (mn), where m is the size of S 1 and n is the size of S 2. However, in the case of calling set_intersection and set_is_equal, the running time is actually closer to T (m, n) = 2mn because both set_intersection and set_is_equal run in T (m, n) = mn times some constant. Compare this with the operation set_is_subset, which runs closer to T (m, n) = mn. Although the complexities of the two methods are the same, calling set_intersection and set_is_equal requires approximately double the time in practice.
Q: Instead of implementing set_is_equal as shown, how could we use other set operations to determine if one set, S1 , is equal to another set, S2 ?
A: In set notation, if S 1 − S 2 = ∅ and S 2 − S 1 = ∅, then S 1 = S 2. Therefore, we could implement this, albeit less efficiently, using two calls to set_difference and two calls to set_size.
Q: Instead of implementing set_intersection as shown, how could we use the set_difference operation to compute the intersection of two sets, S1 and S2 ?
A: In set notation, S 1 ∩ S 2 = S 1
Get Mastering Algorithms with C now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
