CS202 Study Guide

1a. Define sets, operations on sets, and state important set properties

• Why bother with a formal notation in any field of work?
• In what way is a set different from a collection?
• How does one use set-builder notation to translate equations into English to achieve general understanding?

German mathematician Georg Cantor (1845 - 1918) initiated set theory around 1870. He defined "set" as a collection of discrete distinguishable objects having a certain relationship. In some discussions, one states whether or not set members can be duplicated. In the course material, a "set" with repeating members is called a "collection". This distinction between sets and collections holds within computer languages. Since there are variations in definitions for different arenas, be careful to understand the difference within the current situation. Objects (elements, members) can be in more than one set at a time but they are entirely in a set or entirely not in a set.

As noted in the previous paragraph, formal definitions and notations are essential for communication. All parties have to agree on the meaning of words and symbols. Otherwise, confusion and non-understanding reign. Within discrete mathematics, set-builder notation is often used as a shorthand for describing a set's universe, the relationship between members of the set. For instance, Q = {a/b | a,b ∈ Z, b≠0} is a set-theory way of saying, "The membership of set Q is composed of elements that result from dividing a by b such that a and b are elements of set Z and b is not equal to zero".

Review Set Notation and Relations.

1b. Categorize sets into their various types (such as singleton, finite, infinite, equal, null, proper subset, and improper subset) and give a definition of each

• What is the relationship between terminology and symbology?
• What is the difference between null and empty?
• In what way do a universal set and a superset differ?

As discussed earlier, a commonly understood terminology and notation (symbology) must exist for a topic to be discussed. Terminology typically refers to words in natural language, English in this case. "Notation" is short-hand produced by the use of "symbolism", special characters that represent words in natural language. Words, notation, and symbolism are all ways of representing concepts and ideas that enter the human mind. We can consider our thoughts and ideas without having any kind of means of expressing them. But, to communicate them to others, and to have some way of having them understood by others, we need some common way of expressing them. Thus we have terminology, notation, and symbolism.

Sometimes, there is not a one-to-one match between a given term and its notation. One-to-many is often seen. For instance, a null set is the same thing as an empty set. Such sets have various symbols, depending on the document ({ }, Ø, n(X) = 0, |A| = 0). Symbols can have different meanings, depending on the field of work at hand. For example, in other types of mathematics, |A| refers to the absolute value of A. In discrete mathematics, the topic we are studying, |A| refers to the number of elements in set A. The variations in terminology and symbols can lead to confusion so stay alert to the forms used.

Shades of meaning are also important. Definitions of terms and notations can appear to be the same at first but there is often a fine distinction. A good example is the universal set and superset. A superset contains all elements of a particular set but not just those elements. A universal set contains all elements and all sets under consideration. It is a set of all elements of all possible sets. The figure to the right illustrates this idea. Set F is the universal set. Set E is a superset.

Review Types of Sets.

1c. Describe set notation and how that notation is used to perform operations via symbol manipulation

• Given a certain operation on a group of sets, how can that operation be represented diagrammatically?
• Are there cases when an element cannot be a member of more than one set at a time? How so?
• Are partial set memberships allowed? How so?

Operations, characterized as equations, are found in all areas of mathematics. Set theory is no different since it allows for operations to be performed on sets and set members. These operations are strictly defined since there must be a common definition for useful discussion between practitioners.

As noted earlier, an element can be fully a member of more than one set at a time. This is true if we stick solely within the framework of set theory. However, remember that we have to create solutions to situations we find in the real world. Semantics, the true meaning of words within the context of the situation, matter in that world. Take for instance the words YES and NO. In many situations, there is no MAYBE and the answer cannot be YES and NO at the same time. The set "answer" cannot contain the elements "yes" and "no" at the same time. For instance, we cannot take an action and not take that action at the same time. For set theory to have any meaning in the world outside pure mathematics, it has to be interpreted within the context of real-world situations. This provides a means of transitioning theory to reality.

There are many ways to express operations in set theory. We can use equations, generalizations, and Venn diagrams. Venn diagrams use oval shapes to depict set operations. Many people learn and understand better pictorially. Plus, pictures are an aid to understanding what equations, and especially generalizations, are saying. The same is true, for instance, with equations that deal with data that arrives over time. A graph of how the equation behaves each time unit goes a long way to assist in understanding what the equation represents, its behavior over time.

Review:

• Basic Set Operations
• Cartesian Products and Power Sets
• Summation Notation and Generalizations

1d. Apply set definitions, operations, and properties to demonstrate set membership within a specific context

• What are the symbols associated with various set operations and generalizations?
• How does one apply Venn diagrams to illustrate the results of set operations?
• What are important ways that set theory applies to real-life situations?

In other learning goals for this unit, we have seen how precise definitions of terms, symbols, operations, and generalizations make it possible for us to communicate on a given topic. This is also true with set theory. It is important to know the basic means of discussion. Definitions in common use for social conversation are woefully vague for this purpose. 

Beyond precision in definition, there is understandability. If a long equation can be generalized into a shorter equation, that leads to better understanding. Another approach is to draw a picture, a Venn diagram in the case of set theory. Graphs of various kinds are often used in other fields of work. A picture that relates sets to the result of the operations between them can be very valuable for visualizing what equations are trying to convey. 

If our learning is to have value, it has to make a positive difference in the real world. Knowing or developing theory, by itself, has little value unless it is applied to a worthwhile purpose. Here is an example: A great entrepreneurial opportunity is presented by the internet. One can easily set up a store that sells items, even if one never deals with the physical items themselves. (Beware. Running a store profitably is never easy. And, it is fraught with risk. Most stores fail.) Let's say the store carries electronic components, we could say that set S, the store, carries a finite number of components, {c₁, c₂, ..., c_n}. There may be several of each component available, {c_1|1, c_1|2, ... c_1|m}, if c₁ is used as an example. One thing that would help customers know what to buy for what purpose might be a series of well-documented kits, {k₁, k₂, ..., k₃}, that put various components together. Set theory can be used to bring that idea forward. We could think of a generalized set equation such as K₁ = {c_1|2, c_3|1, c_100|5}. This a short-hand way of saying Kit #1 is composed of: two units of Component #1, one unit of Component #3, and five units of Component #100. The Venn diagram to the right illustrates this idea. There is no reason software could not be written to create such diagrams from inventories and parts lists, where the size of the circles represents the number of components available. Links embedded in the image could lead to all manner of detail. To get the number of parts in a kit via this generalization:

$\mathrm{K}_{i \mid \mathrm{n}}=\sum_{a=1, b=1}^{p, y} \mathrm{C}_{\mathrm{a} \mid \mathrm{b}}$

where:

• K_i|n refers to the number of parts (components) in kit I
• p refers to the part number
• y refers to the number of parts of that part number used in kit I

While this last equation may be too complex for the case at hand, it shows that complexity is available when needed. 

Review:

• Basic Set Operations
• Summation Notation and Generalizations

Unit 1 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• collection
• elements
• empty set
• finite
• formal definitions 
• formal notations 
• members
• notation 
• null set
• set
• set-builder notation
• superset
• symbolism 
• terminology
• universal set
• Venn diagram

2a. Describe counting, permutation, and combination rules

• Why is it insufficient to only calculate the number of raw members of a given set?
• How is it possible to estimate the amount of work needed to account for a range of possibilities?
• How are counting techniques used to enumerate options? How so?

In Unit 1, we learned to calculate |<set>|, to count the number of members contained in a given set. While it is important to know how many members a set has, that is only the beginning. We can also enumerate options and evaluate the impact of those options on a given situation. For instance, let's take those members as the itemization of steps in a particular process. If each step can be taken independently of the other steps, it is possible to arrange their accomplishment in numerous ways (permutations), depending on the resources available at any given time. If there is only one step-performance resource available, then only one step can be taken at a time. Yet, "independently" means that it does not matter which step happens at any given time, as long as each step happens only once. Thus, the sequence does not matter, as long as all steps are accomplished. The steps can be ranked according to time-to-accomplish and then do the quickest steps first in order to show rapid progress. If all steps take the same amount of time, then any order will do. It depends on the situation. Similar thinking applies to situations where more than one step-performance resource is available.

Other performance criteria come into play in situations where order matters or when repetition is allowed. For example, consider combinations of steps and how the steps can be arranged if they are taken two at a time. The main point is that mathematics exists to calculate and enumerate the options. We can then study the options and decide which course of action to take. What is most needed in the beginning is to study carefully so that all members of the set, all factors impacting a domain, are known. 

Review Introduction to the Rule of Products.

2b. Compute the number of permutations and combinations of the members of a given set

• What is the difference between the number of a set's subsets and the number of ways to order the members of that same set?
• The "key" to a database management system is a unique attribute value assigned to each record. How does that concept apply to the ordering of a set's members?
• Computing a factorial, N!, is often used in various forms of mathematics. How is it useful in set theory?

We continue our study of various ways to organize members of a set, and how to project the number of ways a set's members can be organized. We can count the members of a set, project the number of subsets of those members, and the number of ways those subset members can be arranged. We can also determine the method by which those members have to be arranged. Such is the benefit of set theory.

There is a certain unity in mathematics. For instance, taking the factorial of a given number, $\prod_{n=1}^{N}$ where 0! = 1, is used, for instance, in Taylor Series, a means of estimating the result of various equations. In set theory, factorials are used to calculate the number of ways the members of a set can be ordered, |<set>|!. This gives the number of unkeyed orderings. If we select a key, some criteria unique to each member, then there is only one ordering. But, if the key is not unique, then the number of possible orderings is ≤ |<set>|! Set theory provides for exact calculation but also allows for estimates, in this sense.

Review Ordering Elements of a Set.

2c. Determine the number of all possible outcomes of a collection of events

• What is the difference between counting groups of ordered elements and counting groups of unordered elements?
• What is an example of cost estimation when creating groups of unordered elements?
• Is it possible, using set theory, to estimate the number of members of a group under imperfect conditions? How so?

Remember it is possible to calculate the number of groupings of a set's members. However, we assumed that there was only one way to order each group. In our present area of learning, we assume that groups can be unordered, that a new group is formed if the order of membership of that group changes. First, determine the number of ordered groups and then determine the number of ways the members of each group can be arranged. (Note that some literature uses the term "subset" for "group").

The ability to list all groups and all options in a given situation can have serious implications for cost estimating. For example, let's take set members as a list of tasks, the sequence of which does not matter. If we list all unordered groups, we assume that each ordering has the same cost to carry out. However, each ordering can be assigned an estimated cost of carrying out that task sequence, if one task is performed at a time. We could, for instance, rank tasks in a subset by their ability to support other members of that subset. Then, of all the arrangements of the original ordered collection of subsets, we could select the one having the highest-ranked member as the first member. In this way, we evaluate all possibilities according to some clear metric. This moves our decision from subjectivity to objectivity, a very data-centric approach to things.

So much of "theory", including set theory, that inhibits its practical application is that theory assumes certain, sometimes unspoken or unrealized, conditions. An example from our readings is the flipping of a coin. For the examples to play out as written, one must assume the coin is evenly balanced so that there is always an equal chance of heads or tails being rolled. But what if the coin is not evenly balanced? What if there is a 75% chance of heads being rolled and 25% of tails. (We assume the coin is thin enough that it cannot land on its side.) We might multiply the count under perfect conditions by the count under imperfect conditions, as a start. One must consider all factors impacting the situation at hand.

Review: 

• Ordering Elements of a Set
• Combinations and the Binomial Theorem

Unit 2 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• combinations 
• enumerate
  
• key
• factorials
• ordered 
• permutations
• subset
• unkeyed orderings 
• unordered 

4a. Discuss how one conclusion leads to another, in the mathematical sense, for a given situation

• What is the difference between a theorem and an axiom?
• Why is investigation important to mathematical systems?
• How do specific definitions impact a mathematical system?

Mathematical systems are evolved through investigation, what is termed "research" in the figure taken from the first reading in this unit. Yet, it is not always top-down. Sometimes, through intuition, imagination, or some other creative process, it is possible that a theory will be postulated. But then, research (investigation) must take place to prove or disprove that theory. Once proven, a theory becomes an axiom, something that can be used to prove more complex theories.

Underlying even research are clear and specific definitions. We must know exactly what we are talking about. If we say "straight line", what does that mean within the context of the mathematical system in which we are engaged? If we use the symbol "+", what exactly does that mean? If we say, "the color is RED", what do we mean by that? Context is important. And, we must be exact within that context so as to transition colloquial speech, which is vague, to technical speech, which is precise.

Review Mathematical Systems.

4b. Write the terms of a logical sequence as a generalized formula

• Why are truth tables not always the best approach to proving a statement to be true or false?
• How can we overcome the limits of truth tables?
• What are two approaches to generalized proofs?

Truth tables are a fine approach to logical proof when there are few variables (facts) involved. But, as the number of variables increases, the size of the truth table increases as does 2V, where V is the number of variables. The table will have a minimum of V columns and 2V rows. For most industrial applications, the use of such a table is intractable, given the time and machinery available. Thus, we need a different approach. This involves the use of Direct and Indirect Proofs.

Direct and Indirect Proofs follow a series of steps that begin with basic axioms and use those as building blocks to build to a final proof or disproof. Direct Proof seeks to demonstrate that a theorem is true. Indirect Proof seeks to prove the theorem is false. We followed the same basic approach when we built truth tables to prove the truth or falsehood of a statement. We started with variables and then added logical statements until the final statement was shown to be true or false under all possible circumstances. Direct and Indirect Proofs generalize this approach.

Review:

• Direct Proof
• Indirect Proof

4c.    Use mathematical induction to prove the validity of logical sequences

• Why is mathematical induction important?
• What are some examples of how induction can explain complex situations?
• Explain the difference between mathematical induction and strong induction?

Mathematical induction and its cousin, strong induction, allow us to overcome the possibility that a situation may contain an infinite number of variables. Strong induction extends mathematical induction in that it allows us to demonstrate additional assertions that are true if a given assertion is proven true by mathematical induction. Real life contains an unending collection of complex situations. Many of these contain variables that are based on previous versions of earlier variables in a never-ending stream. Let's examine one of those.

Zeno's Paradox describes an archer shooting at a target that is some distance, D, away. Once the arrow, A, is set loose, it travels to the half-way point to the target. Then it flies to a point half of the remaining distance. This continues indefinitely, for each step, T. The arrow is always heading for the next half-way point. That being the case, how does the arrow ever reach the target? (We know that it does, eventually, if the archer is accurate.) Here is a solution modeled after the readings' examples. It is drawn from the problem description.

A(0) = D * (1/2⁰)           base case, distance to target prior to arrow being fired.

A(1) = D * (1/2¹)            situational properties

A(2) = D * (1/2²)

...

A(10) = D * (1/2¹⁰)

A(T) → A(T + 1)            inductive step

A(∞) = D * (1/2^T)|_{lim T} → ∞         calculus

A(∞) = D * 0 = 0            final distance to target is 0, the arrow strikes the target

Notice that, in this philosophical context, infinite steps do not necessarily take infinite time. Mathematically, the solution is reasonable. But, is it reasonable from a physics perspective? Can we really take infinite steps in finite time? Calculus, by the way, offers integration as another approach. We can always integrate using this equation: $\int_{0}^{D} d D=D-0=D$. Thus we show that all the small distances add up to the whole distance. (Integration allows us to perform addition of an infinite number of values. (Recall from the readings that ∑ is the Greek letter for summation and S is the Latin letter for summation. So, this is where ∫comes from). In any case, we have two clear and provable indications that the arrow does indeed reach the target, in finite time, even though there appears to be an infinite number of steps in the process.

Review:

• Discussion and Examples
• Strong Mathematical Induction

4d.    employ inductive reasoning to situations where there is sufficient evidence to warrant generalization

• What is the end result of Peano Postulates?
• Give another name for "strong induction".
• What should we look for when we try to engage inductive reasoning?

To paraphrase the last section of this unit, inductive reasoning's foundation began to be laid in the 1800s with the work of Richard Dedekind. He developed a set of axioms that describe the positive integers. Later that same century, Giuseppe Peano refined these axioms, created a logical interpretation, and generalized them into the Peano Postulates. These are the cornerstone of mathematical induction. 

Another name for "strong induction" is "course-of-values induction". From that perspective, we can attempt to apply inductive reasoning by being alert for patterns in an evolving situation or a sequence of events. For instance, Zeno's Paradox is based on the sequence of milestones reached by the arrows. The progress of the situation can be identified by the event leading to each milestone, traveling the distance from the prior milestone to the present milestone, the arrow traveling from the prior halfway point to the present halfway point. We finally realize that A(T) → A(T + 1). From this general statement, we can write a general solution to the problem that does not depend on the specifics (distance to target or any milestone). We can even generalize to the extent that A(T) → A(T + n), where n is any step in the process.

The detection of patterns can be very important to problem-solving. But, so can the lack of discernible patterns. For instance, some computer languages allow memory references beyond predefined vectors and arrays, "memory overruns". This leads to erratic behavior in computer programs. It is rare that any pattern will be observed. That is one reason programmers will restart a program and run it several times under the exact same conditions. If no pattern occurs, they know to look for memory overruns.

Each type of behavior requires a different approach to solve. Apply the approach that leads to the best solution for the situation at hand.

Review:

• Discussion and Examples
• Strong Mathematical Induction

Unit 4 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• axiom
• base case
• course-of-values induction
  
• Direct Proof
• Indirect Proof
• mathematical induction
• memory overruns
• inductive reasoning
• integration
  
• Peano Postulates
• strong induction
• theorem
• variables
  
• Zeno's Paradox
  

 5a. State the definitions of terms that apply to probability within the context of this course

• What is the essential goal of probability?
• Why is a tree of possibilities important?
• How does our ability to count play in probability?
• What are the steps of a basic analysis process?

Fundamentally, probability asks the question, "Out of all possible outcomes, what percentage of the time could a specific outcome, or group of outcomes, be expected to occur, under the specified circumstances?" This is an important consideration, for instance, when deciding on how to allocate resources as a team tries to account for what is "most likely" to happen. This consideration is critical because reaching infinite perfection in many situations requires infinite resources. Yet, resources are always finite. So, we try to rank possibilities by their likelihood of occurring and then account for those.

We are often faced with situations where all the variables are not known. But, we still must make the best choice possible within that situation, although it may turn out we make the wrong choice when all is said and done. (This is not our fault, just the way things turned out.) One approach to making the best choice possible is to build a decision tree based on what we know. Here is an example of such a tree:

Notice that not all paths through the tree are shown and not all paths are labeled. This avoids clutter while adding clarity. The tree shows how one event can lead to another with a certain probability. Player 1 makes a choice (the tree root), then Player 2 can make a choice until no other choices can be made. A player cannot make a choice that has already been made. If we make purely random choices, the tree shows the chance that a particular choice will be made. Once no further choices can be made (a leaf of the tree), we have reached the final event and can calculate the probability of that event. Looking at the tree, the final event D has a probability of $\dfrac{1}{4} \times \dfrac{1}{3} \times \dfrac{1}{2} \times \dfrac{1}{1}= 0.0417 = 4.17\%$. It is thus possible to calculate the probability of subsequent events at any tree node. Clearly, probabilities are not always uniform when considering all possible outcomes.

Being able to count possible combinations of items allows us to calculate the probability that a certain combination will occur. Specific combinations have limited opportunity to occur given a limited universe of items that can be combined in various ways. For example, what is the chance that we will draw four aces from a deck of 52 playing cards? Begin by recalling that $\left(\begin{array}{l} n \\ k\end{array}\right)$  refers to selecting groups of k objects from a base group of n objects, without replacement. That syntax is also written as C(n,k) in various books, papers, and articles. It is calculated as $\dfrac{n!}{k!(n - k)!}$. Dealing four aces from a total of four aces can only be done in C(4,4) = 1 way. Dealing any non-ace card from the rest of the 48 cards can be done by C(48,1) ways. Any five cards can be drawn from a deck of 52 cards in C(52,5) ways, the total number of different five-card hands. Thus, the probability of dealing the four aces is $\dfrac{C(4,4) \times C(48,1)}{C(52,5)}$.

Following a formal process of calculation allows us to overcome the limitations of human intuition. Here is a good general process: 

1. Identify all possible outcomes.
2. Identify all desired outcomes.
3. Calculate probability of each possible outcome.
4. Calculate probability of each desired outcome.

Review Introduction to Discrete Probability.

5b. Calculate conditional probabilities (the probability of event Y occurring if event X has already occurred)

• What is the difference between dependent and independent events?
• Describe a decision tree and show its value.
• What does "conditional probability" mean?
• How does one calculate a conditional probability?

Conditional probability gives the probability that an event will occur after some other event has occurred. Decision trees offer a structure that allows us to compute probabilities for some chain of dependent events. Thus, as trials combine to create events, we can overcome the limits of human intuition using an objective process coupled with a clear framework.

Let's dig deeper into conditional probability by examining an elementary example. Imagine that there are four experiments that we want to conduct, given our research into a particular topic. Because of our limited budget, we can only conduct two of those experiments. We have to choose two of the four possibilities and then proceed to conduct those two. We decide that there is an equal chance of choosing any two of the four experiments (under a uniform distribution) and then an equal chance (under a uniform distribution) of one of the two experiments being successful. What is the chance that a given pair of experiments will be selected? What is the chance that a particular experiment will be successful?

A solution, for this very simple situation, can be visualized with a decision tree, as shown in this figure:

There are only six pairs of experiments that can be selected. Thus, the chance of selecting a given pair is 17%. For each pair, the chance of success is 50%. Thus, the conditional probability of a given experiment's success is 0.50 x 0.17 = 0.09 = 9%, given the situation described. Of course, in reality, scientific experiments may well all fail entirely. But, even then, value is attained since it is important to know what does not work.

Review Conditional Probability.

5c. Compute the probability of independent events

• How does the probability of an independent event affect the probability of a dependent event?
• What is the difference between P(A ∩ B) and P(A | B)?
• What does P(B) mean?

If we ask the value of P(A | B), the conditional probability of Event-A occurring given that independent Event-B has already occurred, we first have to know the probability of independent Event-B, P(B). Event-A is dependent upon Event-B for this calculation. P(B) is calculated as |{B}| / |{all possible events}|.

As an example of an independent event, P(B): if there are 25 blue products out of 100 total products then the probability of a random (uniform distribution) product selection being blue equals 25/100 = 0.25, 25%.

P(A ∩ B) is the probability that Event-A and Event-B occur at the same time, the intersection of Event-A and Event-B. If Event-A and Event-B cannot occur at the same time, they are mutually exclusive,
so P(A ∩ B) = 0.

An example of a dependent event, P(A | B) = P(A ∩ B) / P(B): Assume there are 50 yellow products. Now we ask, what is the chance that a blue product is picked (Event-A) from the total collection of 100 products, knowing that a blue or yellow product was picked (Event-B)? We first have to determine how many products overlap in the total collection of blue and yellow products, | A ∩ B |. Clearly,
{blue} ∩ {blue, yellow} = {blue}. We already know that P(blue) = 0.25. P(blue U yellow) = (25 + 50) / 100 = 0.75. Thus we come to the result that P(A ∩ B) / P(A U B) = 0.25 / 0.75 = 1/3 = P(A | B).

In this way, we arrive at the probability of a dependent event happening as a result of an independent event. This bears greatly on applications such as calculating the probability of a fault occurring in a critical piece of equipment. We start all the independent failures that can occur and then calculate the probability that certain failures can occur at the same time. Clearly, we want to do this objectively and carefully, without worrying about whether or not we would like such things to occur or if we can afford for them to occur or afford to keep them from occurring. Rather, what is important is that we know failure rates and their impacts. If we cannot afford to deal with all possibilities safely, we should not undertake the task. A good contrary example is the report of a failed oil-drilling platform causing death and billions of dollars in heavy pollution because funding was refused by "management" for maintenance and repairs.

Review:

• Independent Events
• Try It Now: Exercises

5d. Estimate the chance of occurrence of a specific event within a collection of events.

• What do we mean by "a collection of events"?
• How does set theory aid us in calculating probabilities?
• What is the difference between discrete and continuous probability?

Discrete probability estimates the probability that a specific (discrete) event will occur. Discrete events are those with a finite number of outcomes. Examples are: rolling a specific number with standard dice or getting heads or tails after flipping a coin. When we flip a coin, there are only two possible outcomes: heads or tails. When we roll a six-sided die, we can only obtain one of six possible outcomes, 1, 2, 3, 4, 5, or 6. 

Continuous probability deals with variables such as the height of a human, values which can vary over an infinitely continuous scale. Whereas discrete probability deals with countable stand-alone events, continuous probability deals with values on a continuous scale. This is much like dealing with integers, which can take on only certain values, vs. floating-point numbers, which can take on an infinite number of values between any two integer values. We do not address continuous probability in this course.

A collection of events is when we refer to some member(s), {M} of a given set of all possible events, {E}. (Note that {M} is a subset of {E}.) For example, the roll of a standard six-sided die can only result in six events, {E} = {1, 2, 3, 4, 5, 6}. We can ask the probability of some set of events occurring. An example is P(M) = P(1) so that {M} = {1}. We can also ask about the independent probability of an even value being rolled, P(M) = P(2, 4, 5) so that {M} = {2, 4, 6}. P(M) = |{M}| / |{E}|

Using set theory we can determine {M1} ∩ {M2} and {M3} U {M4}, both of which are needed to calculate dependent probabilities. P(A | B) = |{A ∩ B}| / |{A U B}|.

Review Sample Spaces, Events, and Their Probabilities.

Unit 5 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• collection of events
• conditional probability
• continuous probability
  
• decision tree
• dependent events
• discrete events 
• discrete probability
• independent events
• leaf
• probability
• random
• root
• trials
• uniform 

7a. State the components of a graph

• What is the basic notion of a graph?
• What is the difference between graphs and trees?
• What is the difference between a directed and undirected graph?
• What are isomorphic graphs?

A basic graph consists of a nonempty set of vertices (nodes, elements), V, and a set of edges, E, which is a subset of the set V × V (every vertex connected to every other vertex). Note that although a set can be empty, a graph cannot exist without at least one vertex. However, a graph CAN exist without edges (links between nodes).

Graphs are a superset of trees and have applications in many domains, not just technical ones (for example, the management domain). We will talk more about trees in the next unit. For now, the difference between a graph and a tree is that (1) graphs have no unique root, while trees have a unique root; (2) graphs can have cycles, while trees cannot have cycles.

Directed and undirected graphs are the two most basic types. When an edge (path) exists between two nodes, a directed graph can only traverse the path in one direction. An undirected graph allows traversal in both directions.

Isomorphic graphs are bijective. There is a one-to-one correspondence between vertices and between edges. There are three features of isomorphic graphs:

1. The order of the graphs are the same, |V| = |V'|
2. The size of the graphs are the same, |E_V| = |E_V'|
3. They share the same degree of sequence, corresponding nodes have the same number of edges.

Review Basic Graph Theory and An Introduction to Graphs.

7b. Describe the two principal graph traversal paradigms

• What are the two main graph traversals discussed in this unit?
• Why are those two approaches important?
• What is one condition that must be met for the two main graph traversals to be accomplished?
• What is an n-cube? Draw an example.

There are two important methods of moving through (traversing) a graph, Eulerian and Hamiltonian. Both refer to undirected graphs. Eulerian traversals touch every edge but only once each. Hamiltonian traversals touch every vertex but only once each. For either traversal type to be used, the graph has to be fully connected, all vertices have to be part of one network. Not every graph is capable of Eulerian or Hamiltonian traversal. So, one cannot depend only on those. One can start designing that way as a means of gaining efficiency. But, to gain effectiveness, traversing the entire graph, one sometimes has to depart from pure Eulerian or Hamiltonian.

In the readings, there is a good example of a graph that does not have an Eulerian traversal, the well-known Koenigsberg Bridge Problem. A good example of a graph that does not have a Hamiltonian traversal is shown in Figure 1.

Figure 1. Example of graph for which there is no Hamiltonian traversal.

An n-dimensional hypercube is also called an n-cube. Basically, this is a graph that can be best visualized in multiple dimensions. The n-cube is typically denoted Qn, where n represents the number of dimensions. Two examples are shown in Figure 2.

Figure 2. Examples of multidimensional graph representations.

A brief application can be found in analog-to-digital conversion. In this case, the number of dimensions is 3, the number of bits used in the conversion. As the arrow moves across the dial of a gauge, it covers a special coating underneath. In so doing, it causes a binary string, a digital signal, to be sent to a computer. This string is interpreted within the computer as a way of converting the angle of the arrow into a 3-bit binary number. An adjacency of readings can be represented by a graph. This approach is illustrated in Figure 3.

Figure 3. Various representations of a 3-cube, Q3, and its use in analog-to-digital conversion.

Review Traversals: Eulerian and Hamiltonian Graphs.

7c. Explain the difference between directed and undirected graph

• What is a graph?
• Draw examples of directed and undirected graphs.
• What is a common notation for listing vertices and edges of graphs?
• What is "direction" an example of, relative to graphs?

As it says in our readings, "A graph is a formal mathematical representation of a network, which is itself a collection of objects connected in some fashion". There are two kinds of graphs, directed and undirected. Directed graphs have arrows to show possible transitions from one vertice (node) to another. If an arrow does not point from Node A to Node B, for instance, a transition from Node A to Node B is not allowed. On the other hand, an undirected graph has no directional arrows to indicate allowed transitions. The assumption is that transition is allowed along both directions of all edges. Figure 1 compares undirected and directed graphs. It also shows a common notation for listing a graph's vertices and edges.

Figure 1. Examples of undirected and directed graphs. Notice the common notation for Vertices (V) and Edges (E).

Direction of transition is one way of adding additional information to a graph. Another way is to show what is needed for a transition to take place in a system whose phases are represented by a graph. For instance, a number along an edge can be used to represent a variable's value that triggers a transition from one system phase (vertice) to a subsequent phase. This is illustrated in Figure 2.

Figure 2. Example of a graph being used to represent system states.

(Notice that there are two states to which the system could be initialized.)

Review Basic Graph Theory.

7d. Use graphs to solve applications involving associated events

• What is graph traversal optimization?
• Why do we care about graph-traversal optimization?
• What are some approaches to graph-traversal optimization?
• Is it reasonable to expect graph traversal to be perfectly optimized in practical situations?

Graph traversal refers to visiting each node in the network. Optimization refers to the cost or benefit of carrying out the traversal. All good planning aims for both efficiency and effectiveness. Efficiency leads to minimizing cost or maximizing benefit. Effectiveness refers to getting the task accomplished according to the task's requirements. It is insufficient to be efficient if effectiveness is not achieved.

Consider the undirected graph in Figure 1. It is but a simple example. Typical examples in reality are much larger, containing many more nodes and edges.

Figure 1. Weighted graph and its associated adjacency matrix.

W(X,Y) represents the weight assigned to the edge between nodes X and Y. Notice that, in this case,
W(X,Y) = W(Y,X), and that W(Y,Y) ≠ 0. The weight refers to the cost or benefit of moving from one node to another along that edge. In an example cost minimization task, we have to visit all nodes, one at a time, at minimum $\sum_{i=1}^{e} W i$, where e is the number of edges employed. For benefit optimization, we would want to maximize the summation. We can only visit a node by moving along an edge from an adjacent node. What can make this a difficult task is an increase in the number of nodes or the graph being directed so that it is not possible to move in both directions from one node to another. Further, it may be the case that not all nodes are connected to all other nodes. Brute-force optimization is not always possible given the time available.

There are various heuristics for optimizing graph traversals. The easiest is Nearest/Furthest Neighbor. If one wants to minimize the summation of weights, one follows the lowest-weighted edge to an adjacent unvisited node. To maximize, the highest-weighted edge is followed. That is the simplest description, but it does not say what to do when there are unvisited nodes in the graph but there are no unvisited nodes adjacent to the presently occupied node. At that point, one has to begin visiting nodes twice in an attempt to visit the remaining nodes.

Review Graph Optimization.

Unit 7 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

• adjacency matrix
• adjacent
• bijective 
• directed graph 
• edges
• elements
• Eulerian traversals
• graph 
• graph traversal
• Hamiltonian traversals
• isomorphic graphs
• Koenigsberg Bridge Problem
• n-cube
• nodes
• optimization
• path
• superset
• trees 
• undirected graph 
• vertex
• vertices
  
• weighted graph