O'Reilly logo

Mastering Algorithms with C by Kyle Loudon

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 1S 2 = and S 2S 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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required