This book covers elementary discrete mathematics for computer science and engineering. It emphasizes mathematical definitions and proofs as well as applicable methods. Topics include formal logic notation, proof methods; induction, well-ordering; sets, relations; elementary graph theory; integer congruences; asymptotic notation and growth of functions; permutations and combinations, counting principles; discrete probability. Further selected topics may also be covered, such as recursive definition and structural induction; state machines and invariants; recurrences; generating functions.
Table of Contents
- What is a Proof?
- Induction I
- Induction II
- Number Theory I
- Number Theory II
- Graph Theory
- Graph Theory II
- Communication Networks
- Relations
- Sums, Approximations, and Asymptotics
- Sums, Approximations, and Asymptotics II
- Recurrences I
- Recurrences II
- Counting I
- Counting II
- Counting III
- Generating Functions
- Introduction to Probability
- Conditional Probability
- Independence
- Random Variables
- Expected Value I
- Expected Value II
- Weird Happenings
- Random Walks
Mathematics for Computer Science
by Eric Lehman and Tom Leighton (PDF) – 339 pages
