TABLE OF CONTENTS
Preface
1 Logic and Proofs
1.1 Propositions
1.2 Conditional
Propositions and Logical Equivalence
1.3 Quantifiers
1.4 Nested
Quantifiers
1.5 Proofs
1.6 Resolution
Proofs
1.7 Mathematical
Induction
Problem-Solving Corner: Mathematical
Induction
1.8 Strong
Form of Induction and the Well-Ordering Property
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
2 The Language of Mathematics
2.1 Sets
2.2 Functions
Problem-Solving
Corner: Functions
2.3 Sequences
and Strings
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
3 Relations
3.1 Relations
3.2 Equivalence
Relations
Problem-Solving
Corner: Equivalence Relations
3.3 Matrices
of Relations
3.4 Relational
Databases
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
4 Algorithms
4.1 Introduction
4.2 Examples
of Algorithms
4.3 Analysis
of Algorithms
Problem-Solving
Corner: Design and Analysis of an Algorithm
4.4 Recursive
Algorithms
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
5 Introduction to Number Theory
5.1 Divisors
5.2 Representations
of Integers and Integer Algorithms
5.3 The
Euclidean Algorithm
Problem-Solving
Corner: Making Postage
5.4 The
RSA Public-Key Cryptosystem
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
6 Counting Methods and the Pigeonhole
Principle
6.1 Basic
Principles
Problem-Solving
Corner: Counting
6.2 Permutations
and Combinations
Problem-Solving
Corner: Combinations
6.3 Algorithms
for Generating Permutations and Combinations
6.4 Introduction
to Discrete Probability
6.5 Discrete
Probability Theory
6.6 Generalized
Permutations and Combinations
6.7 Binomial
Coefficients and Combinatorial Identities
6.8 The
Pigeonhole Principle
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
7 Recurrence Relations
7.1 Introduction
7.2 Solving
Recurrence Relations
Problem-Solving
Corner: Recurrence Relations
7.3 Applications
to the Analysis of Algorithms
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
8 Graph Theory
8.1 Introduction
8.2 Paths
and Cycles
Problem-Solving
Corner: Graphs
8.3 Hamiltonian
Cycles and the Traveling Salesperson Problem
8.4 A
Shortest-Path Algorithm
8.5 Representations
of Graphs
8.6 Isomorphisms
of Graphs
8.7 Planar
Graphs
8.8 Instant
Insanity
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
9 Trees
9.1 Introduction
9.2 Terminology
and Characterizations of Trees
Problem-Solving
Corner: Trees
9.3 Spanning
Trees
9.4 Minimal
Spanning Trees
9.5 Binary
Trees
9.6 Tree
Traversals
9.7 Decision
Trees and the Minimum Time for Sorting
9.8 Isomorphisms
of Trees
9.9 Game
Trees
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
10 Network Models
10.1 Introduction
10.2 A Maximal Flow Algorithm
10.3 The Max Flow, Min Cut Theorem
10.4 Matching
Problem-Solving
Corner: Matching
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
11 Boolean Algebras and Combinatorial
Circuits
11.1 Combinatorial Circuits
11.2 Properties of Combinatorial Circuits
11.3 Boolean Algebras
Problem-Solving Corner: Boolean Algebras
11.4 Boolean Functions and Synthesis of
Circuits
11.5 Applications
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
12 Automata, Grammars, and Languages
12.1 Sequential Circuits and Finite-State
Machines
12.2 Finite-State Automata
12.3 Languages and Grammars
12.4 Nondeterministic Finite-State Automata
12.5 Relationships Between
Languages and Automata
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
13 Computational Geometry
13.1 The Closest-Pair Problem
13.2 An Algorithm to Compute the Convex
Notes
Chapter
Review
Chapter
Self-Test
Computer
Exercises
Appendix
A
Matrices
B
Algebra Review
C
Pseudocode
References
Hints
and Solutions to Selected Exercises
Index