Discrete mathematics for computer scientists

chapter 1 counting
1.1 basic counting
the sum principle
abstraction
summing consecutive integers
the product principle
two-element subsets
important concepts, formulas, and theorems
problems
1.2 counting lists, permutations, and subsets
using the sum and product principles
lists and functions
the bijection principle
k-element permutations of a set
counting subsets of a set
important concepts, formulas, and theorems
problems
1.3 binomial coefficients
pascal s triangle
a proof using the sum principle
.the binomial theorem
labeling and trinomial coefficients
important concepts, formulas, and theorems
problems
1.4 relations
what is a relation？
functions as relations
properties of relations
equivalence relations
partial and total orders
important concepts, formulas, and theorems
problems
1.5 using equivalence relations in counting
the symmetry principle
equivalence relations
the quotient principle
equivalence class counting
multisets
the bookcase arrangement problem
the number of k-element multisets
of an n-element set
using the quotient principle to explain a quotient
important concepts, formulas, and theorems
problems
chapter 2 cryptography and number theory
2.1 cryptography and modular arithmetic
introduction to cryptography
private-key cryptography
public-key cryptosystems
arithmetic modulo n
cryptography using addition mod n
cryptography using multiplication mod n
important concepts, formulas, and theorems
problems
2.2 inverses and greatest common divisors
solutions to equations and inverses mod n
inverses mod n
converting modular equations to normal equations
greatest common divisors
euclid s division theorem
euclid s gcd algorithm
extended gcd algorithm
computing inverses
important concepts, formulas, and theorems
problems
2.3 the rsa cryptosystem
exponentiation mod n
the rules of exponents
fermat s little theorem
the rsa cryptosystem
the chinese remainder theorem
important concepts, formulas, and theorems
problems
2.4 details of the rsa cryptosystem
practical aspects of exponentiation mod n
how long does it take to use the rsa algorithm？
how hard is factoring？
finding large primes
important concepts, formulas, and theorems
problems
chapter 3 reflections on logic and proof
3.1 equivalence and implication
equivalence of statements
truth tables
demorgan s laws
implication
if and only if
important concepts, formulas, and theorems
problems
3.2 variables and quantifiers
variables and universes
quantifiers
standard notation for quantification
statements about variables
rewriting statements to encompass larger universes
proving quantified statements true or false
negation of quantified statements
implicit quantification
proof of quantified statements
important concepts, formulas, and theorems
problems
3.3 inference
direct inference （modus ponens） and proofs
rules of inference for direct proofs
contrapositive rule of inference
proof by contradiction
important concepts, formulas, and theorems
problems
chapter 4 induction, recursion, and recurrences
4.1 mathematical induction
smallest counterexamples
the principle of mathematical induction
strong induction
induction in general
a recursive view of induction
structural induction
important concepts, formulas, and theorems
problems
4.2 recursion, recurrences, and induction
recursion
examples of first-order linear recurrences
iterating a recurrence
geometric series
first-order linear recurrences
important concepts, formulas, and theorems
problems
4.3 growth rates of solutions to recurrences
divide and conquer algorithms
recursion trees
three different behaviors
important concepts, formulas, and theorems
problems
4.4 the master theorem
master theorem
solving more general kinds of recurrences
extending the master theorem
important concepts, formulas, and theorems
problems
4.5 more general kinds of recurrences
recurrence inequalities
the master theorem for inequalities
a wrinkle with induction
further wrinkles in induction proofs
dealing with functions other than nc
important concepts, formulas, and theorems
problems
4.6 recurrences and selection
the idea of selection
a recursive selection algorithm
selection without knowing the median in advance
an algorithm to find an element in the middle half
an analysis of the revised selection algorithm
uneven divisions
important concepts, formulas, and theorems
problems
chapter 5 probability
5.1 introduction to probability
why study probability？
some examples of probability computations
complementary probabilities
probability and hashing
the uniform probability distribution
important concepts, formulas, and theorems
problems
5.2 unions and intersections
the probability of a union of events
principle of inclusion and exclusion for probability
the principle of inclusion and exclusion for counting
important concepts, formulas, and theorems
problems
5.3 conditional probability and independence
conditional probability
bayes theorem
independence
independent trials processes
tree diagrams
primality testing
important concepts, formulas, and theorems
problems
5.4 random variables
what are random variables？
binomial probabilities
a taste of generating functions
expected value
expected values of sums and numerical multiples
indicator random variables
the number of trials until the first success
important concepts, formulas, and theorems
problems
5.5 probability calculations in hashing
expected number of items per location
expected number of empty locations
expected number of collisions
expected maximum number of elements in a location of a hash table
important concepts, formulas, and theorems
problems
5.6 conditional expectations, recurrences, and algorithms
when running times depend on more than size of inputs
conditional expected values
randomized algorithms
selection revisited
quicksort
a more careful analysis of randomselect
important concepts, formulas, and theorems
problems
5.7 probability distributions and variance
distributions of random variables
variance
important concepts, formulas, and theorems
problems
chapter 6 graphs
6.1 graphs
the degree of a vertex
connectivity
cycles
trees
other properties of trees
important concepts, formulas, and theorems
problems
6.2 spanning trees and rooted trees
spanning trees
breadth-first search
rooted trees
important concepts, formulas, and theorems
problems
6.3 eulerian and hamiltonian graphs
eulerian tours and trails
finding eulerian tours
hamiltonian paths and cycles
np-complete problems
proving that problems are np-complete
important concepts, formulas, and theorems
problems
6.4 matching theory
the idea of a matching
making matchings bigger
matching in bipartite graphs
searching for augmenting paths in bipartite graphs
the augmentation-cover algorithm
efficient algorithms
important concepts, formulas, and theorems
problems
6.5 coloring and planarity
the idea of coloring
interval graphs
planarity
the faces of a planar drawing
the five-color theorem
important concepts, formulas, and theorems
problems
appendix a derivation of the more general master theorem
more general recurrences
recurrences for general n
removing floors and ceilings
floors and ceilings in the stronger version of the master theorem
proofs of theorems
important concepts, formulas, and theorems
problems
appendix b answers and hints to selected problems
bibliography
index