Mastering Algorithms With C - Kyle Loudon [54]
Graph algorithms
Algorithms that solve problems modeled by graphs (see Chapter 16). Frequently, graph algorithms use sets to group vertices or edges together. For example, Kruskal's algorithm for computing minimum spanning trees (see the related topics at the end of Chapter 16) uses one set to keep track of edges in the minimum spanning tree as it grows. It uses sets of vertices to avoid cycles in the tree.
Relational algebra
The theoretical query language for database systems. Fundamentally, set theory forms the basis for all query languages. For example, suppose we query a database of problem reports at a software company using SQL (Structured Query Language). We query the database for all developers who are working on problems classified with either a status of OPEN, meaning the developer is working on a problem, or WAIT, meaning the developer has not started. Effectively, this query is the union of all records that have either status.
Description of Sets
Sets are unordered collections of related members in which no members occur more than once. Formally, sets are written with braces around them. Thus, if S is a set containing the members 1, 2, and 3, then S = {1, 2, 3}. Of course, because a set is unordered, this is the same as writing S = {3, 2, 1}. If a member, m, is in a set, S, then membership is indicated by writing m ∈ S ; otherwise, m ∉ S. For example, in the set S = {1, 2, 3}, 2 ∈ S, but 4 ∉ S. To effectively use sets, we should be familiar with some definitions, basic operations, and properties.
Definitions
A set containing no members is the empty set. The set of all possible members is the universe. (Of course, sometimes the universe is difficult to determine!) In set notation:
Two sets are equal if they contain exactly the same members. For example, if S 1 = {1, 2, 3}, S 2 = {3, 2, 1}, and S 3 = {1, 2, 4}, then S 1 is equal to S 2, but S 1 is not equal to S 3. In set notation:
One set, S 1, is a subset of another set, S 2, if S 2 contains all of the members of S 1. For example, if S 1 = {1, 3}, S 2 = {1, 2, 3}, and S 3 = {1, 2}, then S 1 is a subset of S 2, but S 1 is not a subset of S 3. In set notation,
Basic Operations
The union of two sets, S 1 and S 2, is a set, Su , that contains all of the members of S 1 in addition to all of the members of S 2. For example, if S 1 = {1, 2, 3} and S 2 = {3, 4}, then Su = {1, 2, 3, 4}. In set notation:
The intersection of two sets, S 1 and S 2, is a set, Si , that contains only the members that exist in both S 1 and S 2. For example, if S 1 = {1, 2, 3} and S 2 = {1, 2}, then Si = {1, 2}. In set notation:
The difference of two sets, S 1 and S 2, is a set, Sd , that contains all of the members of S 1 except those in S 2. For example, if S 1 = {1, 2, 3} and S 2 = {3, 4}, then Sd = {1, 2}. In set notation:
Properties
The intersection of a set with the empty set is the empty set. The union of a set with the empty set is the original set. This behavior is described by the empty set laws :
The intersection of a set with itself is the original set. Similarly, the union of a set with itself is the original set. This behavior is described by the idempotency laws:
The intersection of a set, S 1, with another set, S 2, results in the same set as the intersection of S 2 with S 1. The same is true for the union of two sets. This behavior is described by the commutative laws:
The intersection of a number of sets can be performed in any order (see Figure 7.1). The same is true for the union of a number of sets. This behavior is described by the associative laws:
The intersection of a set with the union of two others can be carried out in a distributed manner. The same is true for the union of a set with the intersection of two others. This behavior is described by the distributive laws :
The intersection of a set