CS202: Discrete Structures

This course has been designed to provide you with a clear, accessible introduction to discrete mathematics. Discrete mathematics describes processes that consist of a sequence of individual steps (as compared to calculus, which describes processes that change in a continuous manner). The principal topics presented in this course are logic and proof, induction and recursion, discrete probability, and finite state machines. As you progress through the units of this course, you will develop the mathematical foundations necessary for more specialized subjects in computer science, including data structures, algorithms, and compiler design. Upon completion of this course, you will have the mathematical know-how required for an in-depth study of the science and technology of the computer age.

Great thinkers have studied logic since the time of the Greek philosopher Aristotle; its rules serve as the basis for the study of every branch of knowledge − including (and perhaps especially) computer science. Logic is an abstraction and formalization of reasoning we use every day, in mathematics, science, and, in particular, computer science. Logic deals with logical systems consisting of symbols that represent statements that are either true or false, definitions of operations for combining statements (for example, addition is an operation in arithmetic for combining numbers), rules for manipulating statement and operator symbols, and rules for inferring new statements from given statements. In Unit 1 and Unit 2, we will study two logical systems: the propositional calculus and the first order predicate calculus.

The following guidance will help you get started in our study of logic in discrete structures. The definitions and rules are called axioms or postulates (we use these terms synonymously). We use axioms and known true statements to prove the truth or falseness of theorems. A theorem is a statement that has a hypothesis (assumptions) and a conclusion. Much of our work will involve proving theorems. You may notice that several different notations are used in logic, depending on the author, text, or reference. In this course, we use several different notations so that you are introduced to these differences.

Logic is an extensive field of study and selected topics are included in discrete structures. These topics vary depending on the institution or school, course, instructor, and text. To expose you to some of the variation, we use two main resources, as well as include supplementary resources and our own original content. In this unit, we will examine various rules of logic (i.e. negations, conjunctions, and disjunctions) in order to determine how they can create conditional statements, arguments, and rules but also prove the truthfulness or falseness of any argument, whether presented in mathematical terms or in everyday language.

Note: Discrete structures is the term used for discrete mathematics for computer science. Discrete mathematics is often referred to as finite mathematics.

Completing this unit should take you approximately 9 hours.

In the previous unit, we discussed the logical analysis of compound statements, including those comprised of simple statements joined by OR, AND, NOT, etc. operators. This analysis provides us with a better understanding of human reasoning, but cannot be used to determine the validity of the majority of mathematical situations. In some cases, it becomes necessary to separate statements into parts, just as we parse sentences in order to facilitate comprehension.

In this unit, we will learn to analyze and understand the special roles that keywords and predicates (i.e. for all and some) play − exercises that constitute the foundation of predicate calculus.

Completing this unit should take you approximately 8 hours.

In this unit, we will learn the properties of integers, real numbers, rational numbers, irrational numbers, and operations on all of these types of numbers. Our goal will be to learn how to determine the validity or falsity of a mathematical statement via a number of methods, including counterexample and exhaustion. We will apply these methods to not only prove the validity of the properties of the number types we are studying in this unit, but provide a practical approach to them so that future mathematical arguments can be proved or disproved using these methods.

Completing this unit should take you approximately 11 hours.

In the field of computer science, we are often required to prove the correctness of an algorithm. Mathematics has a variety of methods in order to do just that, one of which is known as mathematical induction. In this unit, we will learn to use induction in order to determine whether mathematical sequences are valid or invalid. This lesson is extremely important, because mathematical sequences are the basis for the study of repeated processes.

This unit will present induction first in an abstract form and then through specialized proofs of sequences. We will examine mechanisms for finding the general formula for a sequence and apply mathematical induction to prove a given formula's validity.

Completing this unit should take you approximately 23 hours.

Computer scientists often find themselves working with sets of homogeneous or heterogeneous values. Scientists have devised set theory in order to respond to these situations. In this unit, we will learn the basics of set theory, taking a look at definitions and notations and using the proof methods and counterexample means we introduced earlier to establish set properties.a

Set theory is a fundamental tool of mathematics and often used as the starting point for its study and to define basic concepts, such as functions, numbers, and limits.

Completing this unit should take you approximately 15 hours.

Counting is not always as easy as it sounds. Say, for example, you are asked to arrange three balls of three different colors. What are the possibilities? What if two of them have the same color? This is an example of a set of problems known as "counting problems.” In this unit, we will learn different types of counting using possibility trees and general counting theorems. Once we understand the concepts of counting, we will discuss the probability of event occurrence, which refers to the likelihood that a certain outcome for a given problem set will occur. Events can be dependent or independent, making them subject to different sets of rules. Throughout the unit, we will relate counting and probability to computer science topics such as counting list and array elements, password computation, and brute force attacks.

In this unit, we are going to rely on the Devadas and Lehman reference as primary. Use the Bender and Williamson reference as a supplement.

Completing this unit should take you approximately 15 hours.

In previous sections, we learned about sequences in a general sense. In this unit, we will take a look at a specific type known as a recursive sequence. The unit will first present a number of examples that demonstrate how one computes the terms of a recursive sequence and analyzes certain kinds of problems recursively in order to generate a general recursive sequence. We will then learn to use the proof method of induction to prove the validity or falsity of a recursive sequence.

In this unit, we are going to rely on the Bender and Williamson reference as primary. Use the Devadas and Lehman reference as supplementary. Switching primary references exposes us to some differences in notation and perspective.

Completing this unit should take you approximately 9 hours.

Graphs serve innumerable functions: they can represent communications systems, chart knowledge, and even solve problems. In this unit, we will acquaint ourselves with special kinds of mathematical graphs while discussing graph concepts from degree and vertex to isomorphism. We will then turn to trees, which comprise a special category of graphs, as they serve special purposes and have different structures. We will conclude with a study of tree and graph properties. Trees and graphs have application to artificial intelligence, scheduling problems, and transportation systems.

Completing this unit should take you approximately 8 hours.

Computer language compilers frequently use regular languages (which feature regular expressions) to match patterns within text or perform lexical analysis. This unit will introduce formal languages and state automata to prove the correctness or falsity of a language. We will see that some languages might not be valid for a state automaton, but that we can also define and create state automata for languages defined using regular expressions.

The definition of regular expressions is recursive. This definition and that of regular sets and regular expressions requires careful contemplation on your part.

The topic of formal languages and the related topic of finite state automata are not directly addressed in our two references. Our study of discrete structures has given us the background to develop these topics in instruction paragraphs.

We begin with notation, terminology, and definitions and expressions for formal languages. Then we introduce finite automata and their relationship with regular expressions, and use them to solve problems.

Completing this unit should take you approximately 5 hours.