Sets and Logic | |

Sets | |

Propositions | |

Conditional Propositions and Logical Equivalence | |

Arguments and Rules of Inference | |

Quantifiers | |

Nested QuantifiersProblem-Solving Corner: Quantifiers | |

Proofs | |

Mathematical Systems, Direct Proofs, and Counterexamples | |

More Methods of ProofProblem-Solving Corner: Proving Some Properties of Real Numbers | |

Resolution Proofs | |

Mathematical InductionProblem-Solving Corner: Mathematical Induction | |

Strong Form of Induction and the Well-Ordering Property Notes Chapter Review Chapter Self-Test Computer Exercises | |

Functions, Sequences, and Relations | |

FunctionsProblem-Solving Corner: Functions | |

Sequences and Strings | |

Relations | |

Equivalence RelationsProblem-Solving Corner: Equivalence Relations | |

Matrices of Relations | |

Relational Databases | |

Algorithms | |

Introduction | |

Examples of Algorithms | |

Analysis of AlgorithmsProblem-Solving Corner: Design and Analysis of an Algorithm | |

Recursive Algorithms | |

Introduction to Number Theory | |

Divisors | |

Representations of Integers and Integer Algorithms | |

The Euclidean AlgorithmProblem-Solving Corner: Making Postage | |

The RSA Public-Key Cryptosystem | |

Counting Methods and the Pigeonhole Principle | |

Basic PrinciplesProblem-Solving Corner: Counting | |

Permutations and CombinationsProblem-Solving Corner: Combinations | |

Generalized Permutations and Combinations | |

Algorithms for Generating Permutations and Combinations | |

Introduction to Discrete Probability | |

Discrete Probability Theory | |

Binomial Coefficients and Combinatorial Identities | |

The Pigeonhole Principle | |

Recurrence Relations | |

Introduction | |

Solving Recurrence RelationsProblem-Solving Corner: Recurrence Relations | |

Applications to the Analysis of Algorithms | |

Graph Theory | |

Introduction | |

Paths and CyclesProblem-Solving Corner: Graphs | |

Hamiltonian Cycles and the Traveling Salesperson Problem | |

A Shortest-Path Algorithm | |

Representations of Graphs | |

Isomorphisms of Graphs | |

Planar Graphs | |

Instant Insanity | |

Trees | |

Introduction | |

Terminology and Characterizations of TreesProblem-Solving Corner: Trees | |

Spanning Trees | |

Minimal Spanning Trees | |

Binary Trees | |

Tree Traversals | |

Decision Trees and the Minimum Time for Sorting | |

Isomorphisms of Trees | |

Game Trees | |

Network Models | |

Introduction | |

A Maximal Flow Algorithm | |

The Max Flow, Min Cut Theorem | |

MatchingProblem-Solving Corner: Matching | |

Boolean Algebras and Combinatorial Circuits | |

Combinatorial Circuits | |

Properties of Combinatorial Circuits | |

Boolean AlgebrasProblem-Solving Corner: Boolean Algebras | |

Boolean Functions and Synthesis of Circuits | |

Applications | |

Automata, Grammars, and Languages | |

Sequential Circuits and Finite-State Machines | |

Finite-State Automata | |

Languages and Grammars | |

Nondeterministic Finite-State Automata | |

Relationships Between Languages and Automata | |

Computational Geometry | |

The Closest-Pair Problem | |

An Algorithm to Compute the Convex Hull | |

Appendix | |

Matrices | |

Algebra Review | |

Pseudocode | |

References | |

Hints and Solutions to Selected Exercises | |

Index | |

Table of Contents provided by Publisher. All Rights Reserved. |