Page 10 - Discrete Mathematics and Its Applications

Preface ix

Separatechaptersnowprovideexpandedcoverageofalgorithms(Chapter3)andnumber
theory and cryptography (Chapter 4).
More second and third level heads have been used to break sections into smaller coherent
parts.

Tools for Easier Learning

DifficultdiscussionsandproofshavebeenmarkedwiththefamousBourbaki“dangerous
bend” symbol in the margin.
New marginal notes make connections, add interesting notes, and provide advice to
students.
More details and added explanations, in both proofs and exposition, make it easier for
students to read the book.
Many new exercises, both routine and challenging, have been added, while many ex-
isting exercises have been improved.

Enhanced Coverage of Logic, Sets, and Proof

The satisfiability problem is addressed in greater depth, with Sudoku modeled in terms
of satisfiability.
Hilbert’s Grand Hotel is used to help explain uncountability.
Proofs throughout the book have been made more accessible by adding steps and reasons
behind these steps.
A template for proofs by mathematical induction has been added.
The step that applies the inductive hypothesis in mathematical induction proof is now
explicitly noted.

Algorithms
The pseudocode used in the book has been updated.
Explicit coverage of algorithmic paradigms, including brute force, greedy algorithms,
and dynamic programing, is now provided.
Useful rules for big-O estimates of logarithms, powers, and exponential functions have
been added.

Number Theory and Cryptography

Expanded coverage allows instructors to include just a little or a lot of number theory
in their courses.
The relationship between the mod function and congruences has been explained more
fully.
The sieve of Eratosthenes is now introduced earlier in the book.
Linear congruences and modular inverses are now covered in more detail.
Applications of number theory, including check digits and hash functions, are covered
in great depth.
A new section on cryptography integrates previous coverage, and the notion of a cryp-
tosystem has been introduced.
Cryptographic protocols, including digital signatures and key sharing, are now covered.