Discrete Mathematics and Its Applications, 7/e Kenneth H. Rosen ISBN: 0073383090 Copyright year: 2012 CHAPTER 1 The Foundations: Logic and Proofs 1.1 Propositional Logic 1.2 Applications of Propositional Logic 1.3 Propositional Equivalences 1.4 Predicates and Quantifiers 1.5 Nested Quantifiers 1.6 Rules of Inference 1.7 Introduction to Proofs 1.8 Proof Methods and Strategy CHAPTER 2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices 2.1 Sets 2.2 Set Operations 2.3 Functions 2.4 Sequences and Summations 2.5 Cardinality of Sets 2.6 Matrices CHAPTER 3 Algorithms 3.1 Algorithms 3.2 The Growth of Functions 3.3 Complexity of Algorithms CHAPTER 4 Number Theory and Cryptography 4.1 Divisibility and Modular Arithmetic 4.2 Integer Representations and Algorithms 4.3 Primes and Greatest Common Divisors 4.4 Solving Congruences 4.5 Applications of Congruences 4.6 Cryptography CHAPTER 5 Induction and Recursion 5.1 Mathematical Induction 5.2 Strong Induction and Well-Ordering 5.3 Recursive Definitions and Structural Induction 5.4 Recursive Algorithms 5.5 Program Correctness CHAPTER 6 Counting 6.1 The Basics of Counting 6.2 The Pigeonhole Principle 6.3 Permutations and Combinations 6.4 Binomial Coefficients and Identities 6.5 Generalized Permutations and Combinations 6.6 Generating Permutations and Combinations CHAPTER 7 Discrete Probability 7.1 An Introduction to Discrete Probability 7.2 Probability Theory 7.3 Bayes' Theorem 7.4 Expected Value and Variance CHAPTER 8 Advanced Counting Techniques 8.1 Applications of Recurrence Relations 8.2 Solving Linear Recurrence Relations 8.3 Divide-and-Conquer Algorithms and Recurrence Relations 8.4 Generating Functions 8.5 Inclusion-Exclusion 8.6 Applications of Inclusion-Exclusion CHAPTER 9 Relations 9.1 Relations and Their Properties 9.2 n-ary Relations and Their Applications 9.3 Representing Relations 9.4 Closures of Relations 9.5 Equivalence Relations 9.6 Partial Orderings CHAPTER 10 Graphs 10.1 Graphs and Graph Models 10.2 Graph Terminology and Special Types of Graphs 10.3 Representing Graphs and Graph Isomorphism 10.4 Connectivity 10.5 Euler and Hamilton Paths 10.6 Shortest-Path Problems 10.7 Planar Graphs 10.8 Graph Coloring CHAPTER 11 Trees 11.1 Introduction to Trees 11.2 Applications of Trees 11.3 Tree Traversal 11.4 Spanning Trees 11.5 Minimum Spanning Trees CHAPTER 12 Boolean Algebra 12.1 Boolean Functions 12.2 Representing Boolean Functions 12.3 Logic Gates 12.4 Minimization of Circuits CHAPTER 13 Modeling Computation 13.1 Languages and Grammars 13.2 finite-State Machines with Output 13.3 finite-State Machines with No Output 13.4 Language Recognition 13.5 Turing Machines APPENDIXES A1 Axioms for the Real Numbers and the Positive Integers A2 Exponential and Logarithmic Functions A3 Pseudocode