Topic | Name | Description |
---|---|---|
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 plug-and-chug 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 non-repeating 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 "do-not" 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 course-of-values 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 increasingly-formal 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, real-world 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 Less-Formal Introduction | Basic Graph Theory | We begin with a top-level 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 | Finite-State 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 finite-state 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: Finite-State Machine States | FSM States | This short video explains more about states in a finite-state machine. |
FSM Examples | Review these example designs of relatively simple practical applications of finite-state 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 |