List of Algorithms | |
Instructor's Preface | p. ix |
Student's Preface | p. xiv |
Chapter Summaries | p. xvii |
Pathways Through the Book | p. xx |
Problem Difficulty Rating | p. xxii |
Symbols, Notation, Abbreviations and Conventions | p. xxiii |
Prologue: What Is Discrete Algorithmic Mathematics? | p. 1 |
Mathematical Preliminaries | p. 9 |
Sets, Relations, and Functions | p. 9 |
Some Important Functions | p. 20 |
Growth Rates and Order Notation | p. 30 |
Summation and Product Notation | p. 40 |
Matrix Algebra | p. 50 |
The Language and Methods of Reasoning | p. 56 |
Supplementary Problems | p. 69 |
Algorithms | p. 73 |
Some Examples of Algorithms | p. 73 |
Aspects of AL | p. 88 |
Recursive Algorithms | p. 94 |
Algorithmic Language: Procedures and Functions | p. 105 |
The Analysis of Algorithms | p. 117 |
Supplementary Problems | p. 131 |
Mathematical Induction | p. 135 |
Introduction | p. 135 |
First Examples | p. 137 |
Strong Induction and Other Variants | p. 151 |
Induction and Recursive Algorithms | p. 158 |
Induction and Iterative Algorithms | p. 168 |
How to Conjecture What to Prove | p. 180 |
Inductive Definitions | p. 194 |
Faulty Inductions | p. 201 |
Supplementary Problems | p. 210 |
Graphs and Trees | p. 217 |
Examples and Terminology | p. 217 |
Paths, Cycles and the Adjacency Matrix | p. 236 |
Eulerian and Hamiltonian Paths and Cycles | p. 250 |
Shortest Paths | p. 266 |
Breadth First Search and Depth First Search | p. 278 |
Coloring Problems | p. 285 |
Trees | p. 296 |
Supplementary Problems | p. 311 |
Fundamental Counting Methods | p. 321 |
Introduction | p. 321 |
First Examples: The Sum and Product Rules | p. 322 |
Subtler Examples and Further Rules | p. 329 |
Permutations and Combinations | p. 341 |
Combinatorial Identities and Combinatorial Arguments | p. 348 |
The Binomial Theorem | p. 355 |
Four Common Problems with Balls and Urns | p. 365 |
Generating Functions | p. 375 |
Combinatorial Algorithms | p. 385 |
Algorithmic Pigeonholes | p. 399 |
Supplementary Problems | p. 406 |
Difference Equations | p. 411 |
Introduction | p. 411 |
Modeling with Difference Equations | p. 413 |
Getting Information from Difference Equations | p. 426 |
Terminology and a Fundamental Theorem | p. 433 |
Constant Coefficient Homogeneous Linear Difference Equations | p. 439 |
Qualitative Analysis | p. 451 |
Nonhomogeneous Difference Equations | p. 457 |
Applications to Algorithms | p. 462 |
Variable Coefficients, Sums, and Recent Advances in Computer Algebra | p. 479 |
Nonlinear Difference Equations | p. 484 |
Finite Differences | p. 495 |
Supplementary Problems | p. 508 |
Probability | p. 513 |
Introduction | p. 513 |
Probability Space | p. 517 |
Conditional Probability, Independence, and Bayes' Theorem | p. 527 |
Random Variables and Distributions | p. 539 |
Expected Value | p. 557 |
Variance | p. 569 |
Statistical Estimation | p. 577 |
Applications to Algorithms: Proofs of Prior Claims | p. 586 |
Recursive Methods in Probability | p. 595 |
Supplementary Problems | p. 606 |
An Introduction to Mathematical Logic | p. 611 |
Introduction and Terminology | p. 611 |
The Propositional Calculus | p. 616 |
Validity and Tautology | p. 630 |
Algorithm Verification | p. 637 |
Boolean Algebra | p. 643 |
The Predicate Calculus | p. 663 |
Algorithm Verification Using the Predicate Calculus | p. 676 |
Theorems and Proofs | p. 682 |
Supplementary Problems | p. 689 |
Epilogue: Coming Full Circle with Biology and Minimax Theorems | p. 691 |
DNA Matching | p. 691 |
Algorithmic Mathematics and Minimax Theorems | p. 707 |
Final Problems | p. 717 |
References | p. 723 |
Limits | p. 729 |
Hints and Answers | p. 733 |
Index | p. 761 |
Table of Contents provided by Ingram. All Rights Reserved. |