CSC232: Introduction to CS II
Homework Assignment # 5
Due: Beginning of class on Monday November 2nd, 2009.

Students may work on this assignment in groups of two, in which case only one hard copy with both names needs to be turned in. Also remember to write down the name of the eccentric account that has the electronic copy.

For a set S, we say that A is a subset of S if all of the elements of A are also elements of S. The empty set is a subset of S. Every set is also a subset of itself. The set of all subsets of S is called the power set of S. By mathematical induction, it can be shown that if S has n elements, then the number of elements in its power set is 2ⁿ. For instance, assume S = {1, 2, 3}. The power set of S has the following 2³ = 8 subsets:

    {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}

where the notation {} represents the empty set.

To create the power set, we develop a recursive algorithm that builds the subsets from the bottom up. It uses a chain of recursive calls to isolate, one by one, the individual elements in a set. A return from a recursive call uses the isolated element to add clusters of subsets to the power set. The last return value is the power set. Start with set S of size n. Remove one of the elements, x, from the set to create a new set S^' with n - 1 elements. The new set, S^', has the form S^' = S - {x}. The power set of S^' contains 2^{n - 1} subsets. Adding the element x back into each of these subsets creates another collection of 2^{n - 1} subsets The power set of S is the union of the power set of S^' and the elements in the second collection. The recursive part of the algorithm involves creating the power set of S^'. Just repeat the process by removing an element from S^' to form (S^')', which is a set with n - 2 elements. The stopping condition occurs when removing an element leaves the empty set {}. The power set of the empty set is the one-element set whose only member is {}.

Let us trace the recursive process for S = { A, B, C}. A series of recursive calls removes successive elements from set S.

{A, B, C} ==============> {B, C} ==============> {C} ==============> {} Stop.
                  Step 1: remove A                  Step 2: remove B              Step 3: remove C 

Move back through the recursive chain, in reverse order. At each step, build a new power set by taking the union of the existing power set and the set created by adding the removed element. 

Stopping Condition: Begin to create the power set by adding the empty set {}.

            Set S = {}
            Power Set: { {} }

Step 3: C is the removed element. Create a new subset by adding C to the empty set. The power set now contains the empty set and the singleton set with element C.

            Set S = {C}
            Power Set: { {}, {C} }

Step 2: B is the removed element. Using the existing power set, create a cluster of two more subsets that include B.

            Set S = {B, C}
            Power Set: { {}, {C}, {B}, {B, C} }

Step 1: A is the removed element. Using the existing power set, create a cluster of four more subsets that include A.

            Set S = {A, B, C}
            Power Set: { {}, {C}, {B}, {B, C}, {A}, {A, C}, {A, B}, {A, B, C} }

Write a Java program that implements the above algorithm for generating power sets. Your implementation must use generics to generate power sets for sets of elements of any data type. In my solution, I used the following interface for my recursive method.

       public static <E> Set<Set<E>> generatePowerSet(Set<E> S)

Since Java displays sets using square brackets "[]" instead of curly braces "{}", it will be fine if your program does the same. Make sure to use the interface Java.util.Set to represent sets in your code.

Give your program the name PowerSetGenerator.java. Make sure to upload an electronic copy of the source file on your csc232 eccentric upload folder in a folder called HW\hw5. Also make sure to turn in a stapled hardcopy of your code at the beginning of class on the due date.