Preface xxiOutline for One-Semester Course
This text contains much more material than can be covered in a typical one-semester
course. This diversity of material, however, allows a much broader range of courses to
use the text. For a program that requires a one semester (13-14 weeks) study of discrete
topics, the following outline provides coverage of the fundamental material:
Chapter 1: Sets, Proof Templates, and Induction (8 lectures)
Basic Definitions
Operations on Sets
The Principle of Inclusion-Exclusion
Mathematical Induction
A Second Form of Induction
Chapter 2: Formal Logic (4 lectures)
Introduction to Propositional Logic
Truth and Logical Truth
Predicates and Quantification
Chapter 3: Relations (5 lectures)
Definitions and Operations
Special Types of Relations
Equivalence Relations
Ordering Relations
Chapter 4: Functions (4 lectures)
Basic Definitions
Operations on Functions
The Pigeon-Hole Principle
Chapter 5: Analysis of Algorithms (2 lectures)
Comparing Growth Rates of Functions
Complexity of Programs
Chapter 6: Graph Theory (4 lectures)
Definitions
Connected Graphs
The Kbnigsberg Bridge Problem
Trees
Spanning Trees
Directed Graphs (Optional)
Chapter 7: Counting and Combinatorics (4-5 lectures)
Counting Principles
Permutations and Combinations
Permutations and Combinations with Repetitions
Combinatorial Identities (Optional)
Pascal's Triangle (Optional)
With a semester comprising about 40 lectures, this schedule provides time for exams
and additional time to modify the course to respond to particular curricular and/or student
needs. The one chapter that is quite often left to other courses is Chapter 5. If time permits,