CS202: Discrete Structures

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.

This table defines the notation used in this course.

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.

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.

Read this page to become familiar with the various types of sets. This page is an aid to set terminology and notation.

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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

Read these sections to supplement your understanding of propositional logic.

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

Be sure to review this notation summary since these terms will be used throughout this unit.

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.

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

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.

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

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.

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

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.

"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.

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.

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

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.

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

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.

Also known as course-of-values induction, strong induction adds to mathematical induction by showing that additional assertions hold if mathematical induction holds.

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

We'll begin by laying the foundation of your study of probability. This video will walk through basic concepts you will need to know.

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.

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

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.

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

Events can be dependent or independent of something else. This video considers events whose probability of occurrence is independent of all other events.

Read this section.

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.

Read this page to supplement to your understanding 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.

Read this page to get a sense of recursion from a mathematical basis.

This video explains recursion via illustration.

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

There are many ways to approach recursion. We take a look at those here.

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

In this subunit, we delve into progressions of numbers and their subsets. These progressions can be defined by recursive processes.

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

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.

We begin with a top-level view of graphs by looking at definitions, structure, and dynamics.

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.

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

Transitioning to practicality, we now learn about how data can be structured so that graphs are correctly formed for application.

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

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.

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

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.

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

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.

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

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.

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

Read this page. Take careful note of its definitions.

Getting a good grasp of the definition of a tree and of its components is essential to understanding and making good use of them.

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

Read this page to get a basic overview 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.

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

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.

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

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.

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

Read this article for a quick look at finite state machines.

This short video explains further.

Read this section to go into more detail on FSMs.

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.

This short video explains more about states in a finite-state machine.

Review these example designs of relatively simple practical applications of finite-state machines.

Watch these videos for examples of using FSMs in the real world. They also discuss some subtle issues related to implementing FSMs.