CPSC 170 Program 3: Sets

Introduction to Sets

A set is an unordered collection similar to the bag collection that we discussed in class. However, a set cannot contain duplicate elements, so if an item that is already in a set S is added to S, S does not change. Below are some common set operations:

Union: Takes two sets and returns a new set that contains the elements in the first set and the elements in the second set:

     S1 È S2 = {x | x Î S1  Ú  x Î S2}

Examples:

{a,b,c} È {d,e} = {a,b,c,d,e}
{a,b,c} È {a,b,d} = {a,b,c,d}
{a,b} È {a,b} = {a,b}
{a,b} È {} = {a,b}

Intersection: Takes two sets and returns a new set that contains the elements that are in both sets:

     S1 Ç S2 = {x | x Î S1  Ù  x Î S2}

Examples:

{a,b,c} Ç {d,e} = {}
{a,b,c} Ç {a,b,d} = {a,b}
{a,b} Ç {a,b} = {a,b}
{a,b} Ç {} = {}

Difference: Takes two sets and returns a new set that contains the elements in the first set that are not in the second set:

     S1 - S2 = {x | x Î S1  Ù Ø(x Î S2)}

Examples:

{a,b,c} - {d,e} = {a,b,c}
{a,b,c} - {a,b,d} = {c}
{a,b} - {a,b} = {}
{a,b} - {} = {a,b}

Powerset: Takes a set and returns the set of all subsets of that set. Note that if set S has n elements, then its powerset P(S) has 2ⁿ elements:

     P(S) = {x | x  Í S}

Examples:

S = {}       P(S) = {{}}
S = {a}      P(S) = {{},{a}}
S = {a,b}    P(S) = {{},{a},{b},{a,b}}
S = {a,b,c}  P(S) = {{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

Cartesian Product: Takes two sets S1 and S2 and returns the set of all two-element tuples whose first element is in S1 and second element is on S2. Note that tuples are ordered, so (a,b) != (b,a).
```
     S1 x S2 = {(x,y) | x Î S1  Ù  y Î S2}
```
Examples:
```
{a,b} x {c,d,e} = {(a,c),(a,d),(a,e),(b,c),(b,d),(b,e)}
{a,b} x {a,b} = {(a,a),(a,b),(b,a),(b,b)}
{} x {a,b} = {}
```
Add an element: Although not a formal set operation, and strictly not necessary as long as singleton sets can be constructed and set union is available, it is often useful to simply add an element to a set.

Assignment

Write a SetADT interface for the collection described above, and a LinkedSet implementation of that ADT. Also write a test program that exercises your implementation. Your test program should allow the user to enter elements for two sets S1 and S2, then print each set, their union, their intersection, their difference (S1-S2), their cartesian product (S1xS2), and the powerset for each. It should also allow the user to repeatedly search for and then delete elements from S1. Be sure to label output and prompt for input nicely.

Some things to keep in mind:

You'll need to write a Tuple class to hold the tuples for the cartesian product. This is simple; a tuple just holds two objects, and all it needs is a toString method that gives a string containing the objects in parentheses, separated by a comma. Since no data structure is needed to support it, there's no need to define a separate Tuple interface.
Constructing the powerset will take a little thought. Think of it as a recursive process: To construct the powerset for S={x1,...,xn}, first construct the powerset for S'=S-{x1}. Then P(S) contains all of the sets in P(S') plus each of those sets with x1 added to it. Example:
```
Let S = {a,b,c}.  Then S' = {b,c}, and P(S') = {{},{b},{c},{b,c}}.  

So P(S) = P(S') U  {{a} U x | x in P(S')}
         = {{},{b},{c},{b,c}} U {{a},{a,b},{a,c},{a,b,c}}    
         = {{},{b},{c},{b,c},{a},{a,b},{a,c},{a,b,c}}.    
```
The Usual Good Advice
START EARLY!!! START EARLY!!! START EARLY!!! START EARLY!!! START EARLY!!!

CPSC 170 Program 3: Sets

Introduction to Sets

Assignment

The Usual Good Advice