List price: $178.75
This text is designed for the sophomore/junior level introduction to discrete mathematics taken by students preparing for future coursework in areas such as math, computer science and engineering. Rosen has become a bestseller largely due to how effectively it addresses the main portion of the discrete market, which is typically characterized as the mid to upper level in rigor. The strength of Rosen's approach has been the effective balance of theory with relevant applications, as well as the overall comprehensive nature of the topic coverage.
New/Better coverage of nonhomogeneous linear recurrence relations with constant coefficients is now in the text, rather than in an exercise set.
Generating functions are now covered in a separate section in the main body of the text, expanding the coverage previously found in the appendix.
More coverage of probability theory is included in this edition. New topics covered include the variance of a random variable and Chebyshev's inequality.
Material has been added to the text that demonstrates that discrete mathematics is an active subject with many open questions and with many new discoveries. For example, there is now coverage of Mersenne primes, including the discoveries of new primes in 1997 and 1998, the range for which the Goldbach conjecture has been verified, and the variation of the Tower of Hanoi puzzle with four pegs.
Examples and exercises illustrating the application of discrete mathematics to the protocols and network architecture of the Internet have been added. For example, counting problems involving Internet addresses and Internet Protocol packets, Boolean searching for Web pages and examples about spanning trees and Internet routings have been added.
Many new exercises have been added. These include routine exercises, many requested by current users of the text, as well as challenging exercises, including those that develop new concepts.
Several new biographies have been added, including Charles Peirce, Pafnuty Chebyshev, and Marin Mersenne.
An extensive Web site has been developed to supplement the text for students and instructors. A special icon has been placed throughout the text whenever the Web pages for this book include annotated hyperlinks that can be used to find interesting Web sites relevant to the material under discussion. There are more than 100 different Web reference icons placed throughout the text.
Preface
To the Student
1 The Foundations: Logic, Sets, and Functions
1.1 Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Sets
1.5 Set Operations
1.6 Functions
1.7 Sequences and Summations
1.8 The Growth Functions
2 The Fundamentals: Algorithms, the Integers, and Matrices
2.1 Algorithms
2.2 Complexity of Algorithms
2.3 The Integers and Division
2.4 Integers and Algorithms
2.5 Applications of Number Theory
2.6 Matrice
3 Mathematical Reasoning
3.1 Methods of Proof
3.2 Mathematical Induction
3.3 Recursive Definitions
3.4 Recursive Algorithms
3.5 Program Correctness
4 Counting
4.1 The Basics of Counting
4.2 The Pigeonhole Principle
4.3 Permutations and Combinations
4.4 Discrete Probability
4.5 Probability Theory
4.6 Generalized Permutations and Combinations
4.7 Generating Permutations and Combinations
5 Advanced Counting Techniques
5.1 Recurrence Relations
5.2 Solving Recurrence Relations
5.3 Divide-and-Conquer Relations
5.4 Inclusion-Exclusion
5.5 Applications of Inclusion-Exclusion
6 Relations
6.1 Relations and Their Properties
6.2 n-ary Relations and Their Applications
6.3 Representing Relations
6.4 Closures of Relations
6.5 Equivalence Relations
6.6 Partial Orderings
7 Graphs
7.1 Introduction to Graphs
7.2 Graph Terminology
7.3 Representing Graphs and Graph Isomorphism
7.4 Connectivity
7.5 Euler and Hamilton Paths
7.6 Shortest Path Problems
7.7 Planar Graphs
7.8 Graph Coloring
8 Trees
8.1 Introduction to Trees
8.2 Applications of Trees
8.3 Tree Traversal
8.4 Trees and Sorting
8.5 Spanning Trees
8.6 Minimum Spanning Trees
9 Boolean Algebra
9.1 Boolean Functions
9.2 Representing Boolean Functions
9.3 Logic Gates
9.4 Minimization of Circuits
10 Modeling Computation
10.1 Languages and Grammar
10.2 Finite-State Machines with Output
10.3 Finite-State Machines with no Output
10.4 Language Recognition
10.5 Turing Machines
Appendixes A
A.1 Exponential and Logarithmic Functions
A.2 Pseudocode
A.3 Generating Functions
Suggested Readings
Solutions to Odd-Numbered Exercises
Index of Biographies
Index
This text is designed for the sophomore/junior level introduction to discrete mathematics taken by students preparing for future coursework in areas such as math, computer science and engineering. Rosen has become a bestseller largely due to how effectively it addresses the main portion of the discrete market, which is typically characterized as the mid to upper level in rigor. The strength of Rosen's approach has been the effective balance of theory with relevant applications, as well as the overall comprehensive nature of the topic coverage.
New/Better coverage of nonhomogeneous linear recurrence relations with constant coefficients is now in the text, rather than in an exercise set.
Generating functions are now covered in a separate section in the main body of the text, expanding the coverage previously found in the appendix.
More coverage of probability theory is included in this edition. New topics covered include the variance of a random variable and Chebyshev's inequality.
Material has been added to the text that demonstrates that discrete mathematics is an active subject with many open questions and with many new discoveries. For example, there is now coverage of Mersenne primes, including the discoveries of new primes in 1997 and 1998, the range for which the Goldbach conjecture has been verified, and the variation of the Tower of Hanoi puzzle with four pegs.
Examples and exercises illustrating the application of discrete mathematics to the protocols and network architecture of the Internet have been added. For example, counting problems involving Internet addresses and Internet Protocol packets, Boolean searching for Web pages and examples about spanning trees and Internet routings have been added.
Many new exercises have been added. These include routine exercises, many requested by current users of the text, as well as challenging exercises, including those that develop new concepts.
Several new biographies have been added, including Charles Peirce, Pafnuty Chebyshev, and Marin Mersenne.
An extensive Web site has been developed to supplement the text for students and instructors. A special icon has been placed throughout the text whenever the Web pages for this book include annotated hyperlinks that can be used to find interesting Web sites relevant to the material under discussion. There are more than 100 different Web reference icons placed throughout the text.
Table of Contents
Preface
To the Student
1 The Foundations: Logic, Sets, and Functions
1.1 Logic
1.2 Propositional Equivalences
1.3 Predicates and Quantifiers
1.4 Sets
1.5 Set Operations
1.6 Functions
1.7 Sequences and Summations
1.8 The Growth Functions
2 The Fundamentals: Algorithms, the Integers, and Matrices
2.1 Algorithms
2.2 Complexity of Algorithms
2.3 The Integers and Division
2.4 Integers and Algorithms
2.5 Applications of Number Theory
2.6 Matrice
3 Mathematical Reasoning
3.1 Methods of Proof
3.2 Mathematical Induction
3.3 Recursive Definitions
3.4 Recursive Algorithms
3.5 Program Correctness
4 Counting
4.1 The Basics of Counting
4.2 The Pigeonhole Principle
4.3 Permutations and Combinations
4.4 Discrete Probability
4.5 Probability Theory
4.6 Generalized Permutations and Combinations
4.7 Generating Permutations and Combinations
5 Advanced Counting Techniques
5.1 Recurrence Relations
5.2 Solving Recurrence Relations
5.3 Divide-and-Conquer Relations
5.4 Inclusion-Exclusion
5.5 Applications of Inclusion-Exclusion
6 Relations
6.1 Relations and Their Properties
6.2 n-ary Relations and Their Applications
6.3 Representing Relations
6.4 Closures of Relations
6.5 Equivalence Relations
6.6 Partial Orderings
7 Graphs
7.1 Introduction to Graphs
7.2 Graph Terminology
7.3 Representing Graphs and Graph Isomorphism
7.4 Connectivity
7.5 Euler and Hamilton Paths
7.6 Shortest Path Problems
7.7 Planar Graphs
7.8 Graph Coloring
8 Trees
8.1 Introduction to Trees
8.2 Applications of Trees
8.3 Tree Traversal
8.4 Trees and Sorting
8.5 Spanning Trees
8.6 Minimum Spanning Trees
9 Boolean Algebra
9.1 Boolean Functions
9.2 Representing Boolean Functions
9.3 Logic Gates
9.4 Minimization of Circuits
10 Modeling Computation
10.1 Languages and Grammar
10.2 Finite-State Machines with Output
10.3 Finite-State Machines with no Output
10.4 Language Recognition
10.5 Turing Machines
Appendixes A
A.1 Exponential and Logarithmic Functions
A.2 Pseudocode
A.3 Generating Functions
Suggested Readings
Solutions to Odd-Numbered Exercises
Index of Biographies
Index