| |
| |
| Preface | |
| |
| |
| |
| Logic and Proofs | |
| |
| |
| Propositions | |
| |
| |
| Conditional Propositions and Logical Equivalence | |
| |
| |
| Quantifiers | |
| |
| |
| Proofs | |
| |
| |
| Resolution Proofs | |
| |
| |
| Mathematical Induction | |
| |
| |
| Strong Form of Induction and well ordering Property | |
| |
| |
| |
| The Language of Mathematics | |
| |
| |
| Sets | |
| |
| |
| Functions | |
| |
| |
| Sequences and Strings | |
| |
| |
| Relations | |
| |
| |
| |
| Relations | |
| |
| |
| Relations | |
| |
| |
| Equivalence Relations | |
| |
| |
| Matrices of Relations | |
| |
| |
| Relational Databases | |
| |
| |
| |
| Algorithms | |
| |
| |
| Introduction | |
| |
| |
| Correctness of Algorithms | |
| |
| |
| Analysis of Algorithms | |
| |
| |
| Recursive Algorithms | |
| |
| |
| |
| Introduction to Number Theory | |
| |
| |
| Divisors | |
| |
| |
| Representation of Integers and Integer Algorithims | |
| |
| |
| The Euclidean Algorithm | |
| |
| |
| The RSA Public-Key Cryptosystem | |
| |
| |
| |
| Counting Methods and the Pigeonhole Principle | |
| |
| |
| Basic Principles | |
| |
| |
| Permutations and Combinations | |
| |
| |
| Algorithms for Generating Permutations and Combinations | |
| |
| |
| Introduction to Discrete Probability | |
| |
| |
| Discrete Probability Theory | |
| |
| |
| Generalized Permutations and Combinations | |
| |
| |
| Binomial Coefficients and Combinatorial Identities | |
| |
| |
| The Pigeonhole Principle | |
| |
| |
| |
| Recurrence Relations | |
| |
| |
| Introduction | |
| |
| |
| Solving Recurrence Relations | |
| |
| |
| Applications to the Analysis of Algorithms | |
| |
| |
| |
| Graph Theory | |
| |
| |
| Introduction | |
| |
| |
| Paths and Cycles | |
| |
| |
| 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 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 | |
| |
| |
| Matching | |
| |
| |
| |
| Boolean Algebras and Combinatorial Circuits | |
| |
| |
| Combinatorial Circuits | |
| |
| |
| Properties of Combinatorial Circuits | |
| |
| |
| 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 | |
| |
| |
| Appendices | |
| |
| |
| Matrices | |
| |
| |
| Algebra Review | |
| |
| |
| References | |
| |
| |
| Hints and Solutions to Selected Exercises | |
| |
| |
| Index | |