Topic  Name  Description 

Course Syllabus  Course Syllabus  
1.1: Set Notation and Relations  Set Notation and Relations  Every field of study seeks a common terminology and symbology. While it is possible to think about a subject without knowing its particular language, it is not possible to communicate with others about that subject without some common frame of reference. Thus we begin with the basic terms and notations of set theory. 
Notation  This table defines the notation used in this course. 

Try It Now  Work these exercises to see how well you understand this material. Hints and solutions to some of these exercises are given on the second page. As the course proceeds, new notations and terminology will be introduced as they are needed. Be sure to not plugandchug answers to the exercises. These are to aid your understanding, and it will be difficult to pass the exam if you do not take the exercises seriously. While you should not copy others' work, feel free to discuss these exercises with others who are taking this course. 

1.2: Basic Set Operations  Basic Set Operations  Even as set members are discrete, so are sets themselves. The question we ask about each member is, "Of what sets is it entirely a member?" Although there are no partial set memberships, an entity can be entirely a member of more than one set. So, we can perform various operations on sets, such as add one set to another and subtract one set from another. With questions that require a Yes or No response, there is no dual membership since those are on the same hierarchical level. However, with layered hierarchies, dual 100% membership is possible. For example, we can talk about a car that is also a vehicle. The entity exists entirely in two different sets. Later in the course, we will talk more about hierarchies. 
Types of Sets  Read this page to become familiar with the various types of sets. This page is an aid to set terminology and notation. 

Try It Now  Work these exercises to see how well you understand this material. 

1.3: Cartesian Products and Power Sets  Cartesian Products and Power Sets  While the last section discussed combining sets of individual members to create another set of individual members, here we discuss creating sets of nonrepeating tuples (pairs, triplets, and higher groupings). Later in the course, we will see how to calculate the number of tuples that would be created under various circumstances. 
Try It Now  Work these exercises to see how well you understand this material. 

1.4: Summation Notation and Generalizations  Summation Notation and Generalizations  We have dealt with relatively straightforward notation so far. However, as situations involving sets become more complex, a more compact notation is needed. Here presented is an introduction to that notation. 
Try It Now  Work these exercises to see how well you understand this material. 

2.1: Rule of Products  Introduction to the Rule of Products  If there is some number of different operations, and each operation can be performed in different ways, how many combinations of operations can be performed when the operations are not dependent on one another? This is an important question when trying to determine the number of outcomes for which one must account. 
Try It Now  Work these exercises to see how well you understand this material. 

2.2: Permutations  Ordering Elements of a Set  Often it is the case that the order of things is not important. That is where permutations come in. It enables us to show how many different arrangements can be had of a given set of elements. Of course, this is not true of something like an event stream but we will discuss those later. 
Try It Now  Work these exercises to see how well you understand this material. 

2.3: Partitions of Sets and the Law of Addition  Partitions and Addition Laws  In how many ways can a set be partitioned, broken into subsets, while assuming the independence of elements and ensuring that each element appears in only one subset? This question is often answered, for instance, when deciding how to partition workload across a network of computers. As systems become increasingly complex, the answer allows us to make best use of available resources. 
Try It Now  Work these exercises to see how well you understand this material. 

2.4: Combinations and the Binomial Theorem  Combinations and the Binomial Theorem  We now consider subsets of a given size. How many subsets of a given size can be created from the elements of a given set when order is not a concern? This is a good question when deciding how to partition supply to meet demand when a given number of units are required, without specifying which units. 
Try It Now  Work these exercises to see how well you understand this material. 

3.1: Propositions and Logical Operators  Propositional Logic  Within this subunit, we encounter basic definitions and operators. Fundamental symbology is also presented and discussed. There are several examples that help you understand the math in terms of human language. You will see several ways to say the same thing, while remaining logically and mathematically correct. 
Propositions and Logical Operators  Read these sections to supplement your understanding of propositional logic. 

Try It Now  Work these exercises to see how well you understand this material. 

3.2: Truth Tables and Propositions Generated by a Set  Summary of Logic Notation  Be sure to review this notation summary since these terms will be used throughout this unit. 
Truth Tables and Propositions Generated by a Set  What is in a set and what is not in a set leads to some interesting ways of analyzing truth or falsehood. In this section we use 0 for false (no) and 1 for true (yes). One can also speak in terms of "donot" or "do", "do not perform this action" or "do this action". It is a matter of interpretation, an interpretation that must be established and remain consistent. We can write equations to express these ideas so that many factors can be considered and operated upon in a standard way. This section starts you down that path. 

Try It Now  Work these exercises to see how well you understand this material. 

3.3: Equivalence and Implication  Equivalence and Implication  There are many ways to write the same logical equation. Too, various equations are implied by other equations or are contradicted. This section explores that idea. For instance, changing the terminology used to describe an idea, object, or field of study does not change those from what they are. An example are cloud providers who reinvent basic terminology in distributed systems so that their offering appears to be new and unique. An understanding of this area of thought will allow you to see through marketing hype and to simplify logical equations. Thus, you can bring clarity to your understanding and lower costs to systems described by logical expressions. 
Try It Now  Work these exercises to see how well you understand this material. 

3.4: The Laws of Logic  The Laws of Logic  We will now prepare for the unit on proofs. Essentially, a table of laws is presented and discussed. These are essential to our future study in this topic area. You will find a similarity between laws of logic and laws of algebra. However, just as similarities between the syntax of computer languages can lead you astray, be sure you keep logic and algebra separate. For instance, 1 + 1 does not equal 2 in logic. Rather, 1 + 1 = 1. 
Try It Now  Work these exercises to see how well you understand this material. 

4.1: Mathematical Systems  Mathematical Systems  This page gives an overview of what a mathematical system is and how logic plays an important role in such systems. A discussion on how mathematical facts are developed and organized will help to unify the concepts presented later in the course. The system of propositions and logical operators we developed earlier will serve as a model for our discussion. 
4.2: Direct Proof  Direct Proof  "Brute force" is a term commonly applied to considering all possibilities manually, one at a time, before coming to a conclusion. That works well under simple circumstances but is rarely practical within industrial applications. This section discusses that reality so that you can avoid the "brute force" trap. 
4.3: Indirect Proof  Indirect Proof  Science works to either prove or disprove assertions. This is contrary to those who insist that science seeks only to disprove assertions. This mentality causes the acceptance of assertions unless they are proven false. Therein lies a dangerous way of thinking since it leads to "guilty until proven innocent" once an accusation is made. Assertions are not acceptable as fact until they are proven true. In this section, we consider "proof by contradiction", one side of scientific effort. 
Try It Now  Work these exercises to see how well you understand this material. 

4.4: Propositions over a Universe  Propositions and Truth Sets  As one enters into the realm of advanced technology, one increasingly realizes that a layman's use of terminology and language is too imprecise. Not only does the use of technology require precision, but so does its discussion. Otherwise, it is not possible to establish requirements for a project. Nor is it possible to discover the cause of system problems and thereby get a sense of where to focus one's energies. This subunit gets you thinking along those lines and helps you to understand and avoid the vagueness of common speech. 
Try It Now  Work these exercises to see how well you understand this material. 

4.5: Mathematical Induction  Discussion and Examples  Induction is a means of proving a theorem by showing that if the theorem or assertion is true of any particular case, it is true of the next case in a series, and then showing it is indeed true in any particular case. Our text applies that definition to mathematics by saying mathematical induction is a technique for proving propositions over the positive integers. Mathematical induction reduces to a finite number of steps the proof that all positive integers belong to a specific truth set. The number of steps to complete the proof is the same, regardless of the size of the set or the number of positive integers involved. This is crucial to our discussion of discrete mathematics since it allows us to consider large volumes of evidence while deciding whether to accept or reject an assertion. As we develop automated systems or simply consider what we are hearing on the evening news, we find ourselves having to do exactly that. 
4.6: Strong Induction  Strong Mathematical Induction  Also known as courseofvalues induction, strong induction adds to mathematical induction by showing that additional assertions hold if mathematical induction holds. 
Try It Now  Work these exercises to see how well you understand this material. 

5.1: Introduction  Introduction to Discrete Probability  We'll begin by laying the foundation of your study of probability. This video will walk through basic concepts you will need to know. 
5.2: Sample Spaces, Events, and Their Probabilities  Sample Spaces, Events, and Their Probabilities  Next, we learn about the sample spaces associated with random experiments, about the events that can occur from random experiments, and have a look at a specific event's probability of occurrence. 
Try It Now  Work these exercises to see how well you understand this material. 

5.3: Complements, Intersections, and Unions  Complements, Intersections, and Unions  There are situations where a problem can be solved by representing it as a simpler problem, or one that is similar and already solved. We discuss those opportunities here. 
Try It Now  Work these exercises to see how well you understand this material. 

5.4: Conditional Probability and Independent Events  Conditional Probability  Events can be dependent or independent of something else. This video considers events whose probability of occurrence is independent of all other events. 
Independent Events  Read this section. 

Try It Now  Work these exercises to see how well you understand this material. 

6.1: Introduction  Recursion Demystified  Recursion, something being defined in terms of a different version of itself, can be somewhat mystifying, so read this section for a gentle introduction before we move on to something more formal. 
Recursive Definitions  Read this page to supplement to your understanding of recursion. 

6.2: Transitioning from Informal to Formal  Collected Definitions of Recursion  Now, we will take a look at recursion from informal and formal perspectives that are related. Illustrations give us a practical sense of the matter. This approach prepares us for an increasinglyformal discussion. Read this page to see how recursion exists beyond mathematics and computer programming. 
Explanation and Examples  Read this page to get a sense of recursion from a mathematical basis. 

Illustrating Recursion  This video explains recursion via illustration. 

Sequences and Recursion  This video relates numeric sequences to recursion. There is also a discussion on notation. 

6.3: The Many Faces of Recursion  The Many Faces of Recursion  There are many ways to approach recursion. We take a look at those here. 
Try It Now  Work these exercises to see how well you understand this material. 

6.4: Sequences  Sequences  In this subunit, we delve into progressions of numbers and their subsets. These progressions can be defined by recursive processes. 
Try It Now  Work these exercises to see how well you understand this material. 

6.5: Recursion in the Real World  Predicting Data Sample Values  Read this example of a practical, complex, realworld problem that uses recursion in many ways. The underlying math is not testable, but try to get a sense of its subtle recursive nature. 
7.1: A LessFormal Introduction  Basic Graph Theory  We begin with a toplevel view of graphs by looking at definitions, structure, and dynamics. 
7.2: A Formal Introduction  Introduction to Graphs  Now that you have the general idea, we proceed with the formality required to gain an intuitive idea of what graphs are and what could potentially be done with them. 
Try It Now  Work these exercises to see how well you understand this material. 

7.3: Graph Structures  Data Structures for Graphs  Transitioning to practicality, we now learn about how data can be structured so that graphs are correctly formed for application. 
Try It Now  Work these exercises to see how well you understand this material. 

7.4: Graph Node Connectivity  Connectivity  Which nodes are connected, directly or indirectly? Between which nodes is there a path from one node to another? Those are the questions we deal with now. This is part of the topic of graph traversal, encountering a series of connected nodes in a graph or subgraph. 
Try It Now  Work these exercises to see how well you understand this material. 

7.5: Graph Traversals  Traversals: Eulerian and Hamiltonian Graphs  At times, we need a way to encounter every node in a graph. This page discusses how to do just that by using two important kinds of graphs. 
Try It Now  Work these exercises to see how well you understand this material. 

7.6: Graph Optimization  Graph Optimization  A common thread that connects all the topics in this unit is the opportunity to optimize (maximize or minimize) some quantity that is associated with a graph. For instance, we may decide to select a path from one node to another based on the weight of the connections between those nodes. The weights refer to some aspect of the situation at hand, like distance, cost, or importance. 
Try It Now  Work these exercises to see how well you understand this material. 

7.7: Planarity and Colorings  Planarity and Colorings  Annotating a graph so that it contains additional information is very important as the complexity of an application increases. Generally, the more complex the technology, the more precise needs to be its descriptive information. 
Try It Now  Work these exercises to see how well you understand this material. 

8.1: Introduction  Quick Introduction to Trees  Read this page. Take careful note of its definitions. 
Formal Introduction to Trees  Getting a good grasp of the definition of a tree and of its components is essential to understanding and making good use of them. 

Try It Now  Work these exercises to see how well you understand this material. 

8.2: Spanning Trees  Overview of Spanning Trees  Read this page to get a basic overview of spanning trees. 
Detailed Discussion of Spanning Trees  A spanning tree T of an nondirected graph G is a subgraph that itself is a tree that includes all vertices of G, with a minimum possible number of edges. In general, a graph may have several spanning trees. This concept has a lot of implications regarding optimization of tree structure and traversal. Let us have a look at this idea. 

Try It Now  Work these exercises to see how well you understand this material. 

8.3: Rooted Trees  Rooted Trees  We can separate rooted trees from nondirected trees by noting that a rooted tree contains a special vertex, called the root. If we choose any other vertex in the tree, we know that there is a unique path from the root to that vertex. The implication is that there is a hierarchy of vertices. Lets us take a deep look at rooted trees. 
Try It Now  Work these exercises to see how well you understand this material. 

8.4: Binary Trees  Binary Trees  Binary trees are special cases of rooted trees. Binary trees have zero or more nodes. Each node has at most two children. A node without children is called a leaf. This type of tree is the most commonly encountered in practice. That is why we spend additional time with them. 
Try It Now  Work these exercises to see how well you understand this material. 

9.1: Introduction  FiniteState Machine Overview  Read this article for a quick look at finite state machines. 
More on Finite State Machines  This short video explains further. 

State Machines  Read this section to go into more detail on FSMs. 

9.2: State Transition Diagrams  State Transition Diagrams  How we illustrate a finitestate machine has a great deal to do with how well others will understand our design. There is also an opportunity for objective review and evolution of the underlying system. This video continues with a discussion on the design of a combination lock. 
9.3: FiniteState Machine States  FSM States  This short video explains more about states in a finitestate machine. 
FSM Examples  Review these example designs of relatively simple practical applications of finitestate machines. 

9.4: Putting the Basics to Use  Putting the Basics to Use  Watch these videos for examples of using FSMs in the real world. They also discuss some subtle issues related to implementing FSMs. 
Study Guide  CS202 Study Guide  
Course Feedback Survey  Course Feedback Survey 