# Discrete Mathematics and Its Applications

###### Kenneth H. Rosen
Publisher:
McGraw-Hill
Publication Date:
2012
Number of Pages:
1072
Format:
Hardcover
Edition:
7
Price:
257.00
ISBN:
9780073383095
Category:
Textbook
BLL Rating:

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Allen Stenger
, on
04/16/2015
]

This is a very polished and complete text, now in its seventh edition, and probably the dominant text in the field. Overall, however, I wasn’t very happy with this book. It doesn’t have a good narrative flow, but hops from subject to subject. I also thought the examples were weak; they are numerous, but most seem boring and contrived. You don’t come away from this book with the idea that discrete math is an exciting subject. The promised applications, also numerous, are mostly to computer science rather than to real-world problems. On the plus side, the book is thorough and comprehensive, there are copious exercises, and the book is well-supported by the publisher with supplemental materials.

The book is aimed at the sophomore or higher level (Preface, p. xii). Knowledge of calculus is optional, and items requiring it are flagged. The book is slanted heavily towards computer science, especially in the later chapters. The last chapter, on finite-state machines and language recognition, is on a subject I would consider pure computer science (compilers) and not mathematics at all.

Because the prerequisites are so low, the book does only a small amount of analysis of the performance of algorithms. The big-O notation is introduced and the time complexity of a few simple algorithms is analyzed. The book does cover the Master Theorem that gives the asymptotic behavior of a function satisfying a recursion (p. 532).

The introduction to proofs aspects of the book are very strong. There are 40 pages early on that discuss all the common proof techniques, with many examples of correct and incorrect proofs. More specialized techniques are shown throughout the book, such as proof by induction and counting proofs.

Very Good Feature: The companion web site has a supplemental 450-page book (in PDF format) edited by Rosen and John G. Michaels, Applications of Discrete Mathematics. Each chapter is cross-referenced to the sections of the present book that are its prerequisites. These applications are also primarily to computer science, but there are others such as a chapter on apportionment and a chapter on voting procedures.

The book has a massive amount of ancillary material, mostly online on the companion web site. There is a student site and an instructor site. The student site is mostly “more of the same”, with additional examples and exercises that are not any easier or harder than those in the book. It also has the excellent applications book (mentioned above) and two essays, one on proof techniques and one on common errors in discrete math. I did not examine the instructor site, but it contains various pre-made materials for teaching and testing. There are also two print manuals available, a student’s solutions guide (complete solutions to all odd-numbered problems, rather than the hints given in the back of the book), and an instructor’s resource guide (complete solutions the the even-numbered problems, along with a test bank, instructor tips, and sample syllabi).

I reviewed the text in several electronic forms. CourseSmart for desktop computers uses a Flash application and appears to be rendering PDF pages from the print book; they are sharp, you can select the text, and there are no symbol formatting problems such as are often seen on Kindle math books. There’s also a variant for iOS and Android devices. I tested the iPad version; it is usable but not as nice as the desktop version. It also renders pages from the book, but you have to zoom in to read them because the screen is so much smaller, and they appear to be high-resolution JPEGs and so the characters are a little fuzzy, but the text is still selectable. Another nice feature of all CourseSmart versions is that you can download a copy of the book and work offline.

I also looked a little at the SmartBook version. This also presents the text in its printed form, but optionally puts yellow highlighting on the most important parts. It also has a lot of interactive exercises from the book. This application tries to shepherd you on the most efficient path through the book, but I found it more annoying than useful, so I did not spend much time on it. (The SmartBook version has only some chapters of the book, with others marked “Coming Soon”.)

There is also a Kindle version but I did not examine that. It is described as a “print replica”, a Kindle format that is similar to a PDF and so avoids the formatting problems of plain Kindle books.

This book competes head-on with Epp’s Discrete Mathematics with Applications. Both are ridiculously expensive, listing at about $250 for Rosen and$350 for Epp. Both books cover about the same topics, are slanted toward computer science, and have large amounts of supporting material. Epp is more leisurely, does not go into as much depth as Rosen, uses more diagrams, and the examples and exercises are easier. The introduction to proof material in Epp is not as concentrated and is mixed in with a lot of the mathematical exposition, especially in number theory and recursions. One seemingly minor point that I think makes a lot of difference is that Epp has a more welcoming layout, with lots of white space and many subheadings to help you find your way.

There are a couple of other good books that are aimed differently but have strengths of their own, as well as much more reasonable prices. Ross & Wright’s Discrete Mathematics is aimed slightly lower (at freshmen) but has excellent examples. Aigner’s Discrete Mathematics is more mathematical and has less coverage but is a very good introduction for math majors. It has no material about logic or transition to proofs, and assumes you already know these things. It is a translation of a German work and is probably aimed higher, at upper-division undergraduates.

Allen Stenger is a math hobbyist and retired software developer. He is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis.

• Preface
• The Companion Website
• To the Student
• 1 The Foundations: Logic and Proofs
• 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
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• 3 Algorithms
• 3.1 Algorithms
• 3.2 The Growth of Functions
• 3.3 Complexity of Algorithms
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• 7 Discrete Probability
• 7.1 An Introduction to Discrete Probability
• 7.2 Probability Theory
• 7.3 Bayes' Theorem
• 7.4 Expected Value and Variance
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• 12 Boolean Algebra
• 12.1 Boolean Functions
• 12.2 Representing Boolean Functions
• 12.3 Logic Gates
• 12.4 Minimization of Circuits
• End-of-Chapter Material
• 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
• End-of-Chapter Material
• Appendix 1. Axioms for the Real Numbers and the Positive Integers
• Appendix 2. Exponential and Logarithmic Functions
• Appendix 3. Pseudocode