xxii Preface
however, this material gives a good overview of the relationship between programs and
their complexity.
Many variations can be made based on what other courses are included in the
program. In some programs, topics in Chapters 1 through 4, particularly basic properties
of sets and functions, will be covered in prerequisite courses and may be reviewed quickly
in a discrete mathematics course. The sections on Induction, the Principle of Inclusion-
Exclusion, and the Pigeon-Hole Principle, however, should normally be covered. In other
programs, if material on the analysis of algorithms has already been discussed in computer
science courses, then Chapter 4 might be a review, to a certain extent, and take less time.
Optionally, material on directed graphs might be eliminated. Depending on the needs of
the program, the lectures saved above may be spent on other material on the book.Outline for a One-Quarter Course
With only 30 lectures in a one-quarter course, the syllabus presented earlier needs to be cut
to about 27 lectures.
Provided the material of Chapter 5 is covered in other computer science courses, this
chapter can be omitted without difficulty. If other mathematics courses explain the idea of
a function, the only necessary material in Chapter 4 is the Pigeon-Hole Principle, which
can save at least one lecture. Finally, eliminating the material on directed graphs should
allow the basic ideas of graph theory to be covered in four lectures. In addition, the nine
lectures scheduled for Chapters 1 and 2 may be shortened one or two lectures.
Incorporating these suggestions, the following is a possible syllabus for a one-quarter
course (10 weeks):
Chapter 1: Sets (7 lectures)
Basic Definitions
Operations on Sets
The Principle of Inclusion-Exclusion
Mathematical Induction
A Second Form of Induction
Chapter 2: Formal Logic (3 lectures)
Introduction to Propositional Logic
Truth and Logical Truth
Predicates and Quantification
Chapter 3: Relations (4 lectures)
Definitions and Operations
Special Types of Relations
Equivalence Relations
Ordering Relations
Chapter 4: Functions (3 lectures)
Basic Definitions
Operations on Functions
The Pigeon-Hole Principle
Chapter 6: Graph Theory (4 lectures)
Definitions