1: An Introduction to Combinatorial Problems and Techniques
Section 1.1 The Time to Complete a Project
Section 1.2 A Matching Problem
Section 1.3 A Knapsack Problem
Section 1.4 Algorithms and Their Efficiency
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
2: Sets, Relations, and Functions
Section 2.1 Set Operations
Section 2.2 Equivalence Relations
Section 2.3_ Partial Ordering Relations
Section 2.4 Functions
Section 2.5 Mathematical Induction
Section 2.6 Applications
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
3: Coding Theory
Section 3.1 Congruence
Section 3.2 The Euclidean Algorithm and Diophantine Equations
Section 3.3 The RSA Method
Section 3.4 ErrorDetecting and ErrorCorrecting Codes
Section 3.5 Matrix Codes
Section 3.6 Matrix Codes That Correct All SingleDigit Errors
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
4: Graphs
Section 4.1 Graphs and Their Representations
Section 4.2 Paths and Circuits
Section 4.3 Shortest Paths and Distance
Section 4.4 Coloring a Graph
Section 4.5 Directed Graphs and Multigraphs
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
5: Trees
Section 5.1 Properties of Trees
Section 5.2 Spanning Trees
Section 5.3 DepthFirst Search
Section 5.4 Rooted Trees
Section 5.5 Binary Trees and Traversals
Section 5.6 Optimal Binary Trees and Binary Search Trees
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
6: Matching
Section 6.1 Systems of Distinct Representatives
Section 6.2 Matchings in Graphs
Section 6.3 A Matching Algorithm
Section 6.4 Applications of the Algorithm
Section 6.5 The Hungarian Method
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
7: Network Flows
Section 7.1 Flows and Cuts
Section 7.2 A Flow Augmentation Algorithm
Section 7.3 The MaxFlow MinCut Theorem
Section 7.4 Flows and Matchings
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
8: Counting Techniques
Section 8.1 Pascal’s Triangle and the Binomial Theorem
Section 8.3 Permutations and Combinations
Section 8.4 Arrangements and Selections with Repetitions
Section 8.5 Probability
Section 8.6* The Principle of InclusionExclusion
Section 8.7* Generating Permutations and r Combinations
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
9: Recurrence Relations and Generating Functions
Section 9.1 Recurrence Relations
Section 9.2 The Method of Iteration
Section 9.3 Linear Difference Equations with Constant Coefficients
Section 9.4* Analyzing the Efficiency of Algorithms with Recurrence Relations
Section 9.5 Counting with Generating Functions
Section 9.6 The Algebra of Generating Functions
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
10: Combinatorial Circuits and Finite State Machines
Section 10.1 Logical Gates
Section 10.2 Creating Combinatorial Circuits
Section 10.3 Karnaugh Maps
Section 10.4 Finite State Machines
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
Appendix A: An Introduction to Logic and Proof
Section A.1 Statements and Connectives
Section A.2 Logical Equivalence
Section A.3 Methods of Proof
Historical Notes
Supplementary Exercises
Suggested Readings
Appendix B Matrices
Historical Notes
Appendix C The Algorithms in This Book
Bibliography
Answers to oddnumbered exercises
Index
