| | | List of Algorithms |
| 0.13 | | Contents |
| 0.17 | | Symbols, Notation and Conventions |
| 0.17 | A. | Algorithms |
| 0.17 | B. | Notation related to problems |
| 0.17 | C. | Numbering conventions |
| 0.18 | D. | General mathematical notation |
| | E. | Specific mathematical symbols |
| 1 | Prologue | What Is Discrete algorithmic Mathematics? |
| 8 | Chapter 0. | Mathematical Preliminares |
| 8 | 0.1 | Sets |
| 18 | 0.2 | Relations |
| 21 | 0.3 | General Properties of Functions |
| 26 | 0.4 | Some Important Functions |
| 39 | 0.5 | Summation and Product Notation |
| 49 | 0.6 | Matrix Algebra |
| 56 | 0.7 | Proof and Logic Concepts |
| 66 | | Supplementary Problems |
| 68 | Chapter 1. | Algorithms |
| 68 | 1.1 | Introduction |
| 71 | 1.2 | The Notion of an Algorithm |
| 88 | 1.3 | Algorithmic Language |
| 100 | 1.4 | Recursive Algorithms |
| 110 | 1.5 | Algorithmic Language - Procedures and Functions |
| 122 | 1.6 | The Analysis of Algorithms |
| 134 | | Supplementary Problems |
| 137 | Chapter 2. | Mathematical Induction |
| 137 | 2.1 | Introduction |
| 139 | 2.2 | Examples of Induction |
| 155 | 2.3 | Strong Induction and Other Variants |
| 162 | 2.4 | How to Guess What to Prove |
| 170 | 2.5 | Faulty Inductions |
| 178 | 2.6 | Induction and Algorrithms |
| 184 | 2.7 | Inductive Definitions |
| 190 | | Supplementary Problems |
| 194 | Chapter 3. | Graphs and Trees |
| 194 | 3.1 | Introduction and Examples |
| 201 | 3.2 | Terminology and Notation |
| 214 | 3.3 | Paths and Cycles - The Adjacency Matrix |
| 227 | 3.4 | Eulerian and Hamiltonian Paths and Cycles |
| 240 | 3.5 | A Shortest Path Algorithm |
| 249 | 3.6 | Breadth First Search and Depth First Search |
| 256 | 3.7 | Coloring Problems |
| 267 | 3.8 | Trees |
| 281 | | Supplementary Problems |
| 288 | Chapter 4. | Fundamental Counting Methods |
| 288 | 4.1 | Introduction |
| 289 | 4.2 | First Examples: The Sum and Product Rules |
| 295 | 4.3 | Subtler Examples and the Division Rule |
| 303 | 4.4 | Permutations and Combinations |
| 310 | 4.5 | Combinatorial Identities aand Combinatorial Arguments |
| 315 | 4.6 | The Binomial Theorem |
| 325 | 4.7 | Four Common Problems with Balls and Urns |
| 335 | 4.8 | Inclusion-Exclusion |
| 343 | 4.9 | Combinatorial Algorithms |
| 357 | 4.10 | Algorithmic Pigeonholes |
| 364 | | Summary |
| 364 | | Supplementary Problems |
| 366 | Chapter 5. | Difference Equations |
| 366 | 5.1 | Introduction |
| 368 | 5.2 | Modeling with Different Equations |
| 379 | 5.3 | Getting Information from Difference Equations |
| 387 | 5.4 | Solving Difference Equations: Preliminaries |
| 390 | 5.5 | Secord-Order, Constant Coefficient, Homogeneous Difference Equations |
| 403 | 5.6 | Difference Equations of Arbitrary Order |
| 408 | 5.7 | Nonhomogeneous Difference Equations |
| 415 | 5.8 | The General First-Order Linear Difference Equation |
| 420 | 5.9 | Applications to Algorithms |
| 433 | | Summary |
| 434 | | Supplementary Problems |
| 438 | Chapter 6. | Probability |
| 438 | 6.1 | Introduction |
| 441 | 6.2 | Probability Space |
| 451 | 6.3 | Conditional Probability, Independence, and Bayes' Theorem |
| 465 | 6.4 | Random Variables and Probability Distributions |
| 480 | 6.5 | Expected Value and Variance |
| 493 | 6.6 | Applications to Algorithms: Proofs of Prior Claims |
| 508 | 6.7 | Recursive Methods in Probability |
| 518 | | Supplementary Problems |
| 522 | Chapter 7. | An Introduction to Mathematical Logic |
| 522 | 7.1 | Introduction, Terminology, and Notation |
| 528 | 7.2 | The Propositional Calculus |
| 551 | 7.3 | Natural Deduction |
| 559 | 7.4 | Algorithm Verification |
| 564 | 7.5 | Boolean Algebra |
| 581 | 7.6 | The Predicate Calculus |
| 594 | 7.7 | Algorithm Verification Using the Predicate Calculus |
| 600 | 7.8 | Wffs and Algorithms |
| 606 | | Supplementary Problems |
| 608 | Chapter 8. | Algorithmic Linear Algebra |
| 608 | 8.1 | Introduction |
| 610 | 8.2 | Gaussian Elimination: Square Systems |
| 625 | 8.3 | Gaussian Elimination: General Case |
| 640 | 8.4 | Gaussian Elimination: A Closer Look |
| 646 | 8.5 | Algorithm Lu-Gauss |
| 655 | 8.6 | Gaussian Elimination and Matrix Algebra |
| 666 | 8.7 | Vector Spaces: Definition and Examples |
| 675 | 8.8 | Vector Spaces: Basic Theory |
| 693 | 8.9 | Eigenvalues |
| 707 | 8.10 | Markov Chains |
| 718 | | Supplementary Problems |
| 722 | Chapter 9. | Infinite Processes in Discrete Mathematics |
| 722 | 9.1 | Introduction |
| 725 | 9.2 | Sequences and Their Limits |
| 738 | 9.3 | Growth Rates and Order Notation |
| 746 | 9.4 | Finite Differences and Factorial Functions |
| 757 | 9.5 | Infinite Series and Their Summation |
| 773 | 9.6 | Generating Function |
| 784 | 9.7 | Approximation Algorithms |
| 795 | | Supplementary Problems |
| 798 | Epilogue. | Sorting Things Out with Sorting |
| 798 | E.1 | Comparison of Previous Methods |
| 802 | E.2 | The Complexity of SOrting by Comparisons |
| 815 | E.3 | Quicksort |
| 829 | | Final Problems |
| | | References |
| | | Appendixes |
| | 1. | Summary of Algorithmic Language |
| | 2. | Abbreviations |
| | | Hints and Answers |
| | | Index |
