Algorithms and Data Structures Wiki

Basics[]

A "set" is just some collection of "things", for example the set of three people { Anna, Bob, Caesar } or the set of four numbers { 496, 6, 28, 8128 }. The things contained in a set are called "elements" of that set, so 28 is an element of the set { 6, 28, 496 }, whereas 42 is not.

Note that sets are not ordered, i.e. { 23, 42 } = { 42, 23 }. They also don't care about duplicates, i.e. { 6, 6, 28 } = { 6, 28 }. However, I will usually write my example sets without duplicates and often they will look ordered. Note that if the input to a programming problem is a set, you might come across duplicates and the set might not be ordered. Be careful, watch out for that!

The "size" or "cardinality" of a set A is written as #A or |A|. It tells us how many elements are in the set, for example |{6, 28, 6}| = 2. There are finite and infinite sets, meaning they have finitely or infinitely many elements. Even though infinite sets are mathematically nice, they play only a very little (if any) role in TopCoder problems, so I will only discuss finite sets here.

We are programmers and want to work with sets, therefore we have to hold them in some data structures. Even though sets don't offer an idea of order, in your program you have them stored somehow, maybe in an array that contains the elements. Because of this, it's legitimate to talk about the "first element" of a set or the "i-th element". When I say something like that, remember that by this I mean the "first element in my representation of the set" or similarly the "i-th".

A "subset" of some set B is a set that contains only elements of B. For example, here are all subsets of the set { 3, 1, 4 }:

{ }, { 3 }, { 1 }, { 4 }, { 3, 1 }, { 3, 4 }, { 1, 4 }, { 3, 1, 4 }

The first set in that list is a special set, called the "empty set". Naturally, the empty set is a subset of any set. The last set is also a bit special, since it's the same as the whole set B. You can see that every set is a subset of itself.

If you have a set of N elements, how many subsets are there? In the above example, N=3 and we had eight subsets. The answer is 2N, in the example 23 = 8. Why is this? To build our subset, let's start with the first element. We can either include it or leave it out. A choice between two possibilities. Then we go on to the next element and make a choice to include it or not. And so on. For each of the N elements, you have two choices, so there are 2N possible resulting subsets. Convince yourself that with this method you'll really get each subset exactly once. You will not create a subset twice and every possible subset will be generated. We will also see this again a little bit later.

Since 2N is a fairly easy formula, you will probably never see a problem that just asks for the number of subsets of a set. But it's good to know, since you might need it as part of a larger task.

Set theory is a large large part of mathematics and far more complicated and richer than what I'll cover here, since here I'm more interested in basic computational needs. For a start on more, look at the Math Wiki.