1. Introduction proofs propositions predicates
and quantifiers truth tables first order logic
satis fiability pattern of proof proofs by cases
proof of an implication proof by contradiction
proving iff sets proving set equations russells
paradox well-ordering principle induction invariants
strong induction structural induction pigion hole
principle parity number theory divisibility
gcd euclids algorithm primes
2. Graph theory simple graphs isomorphism subgraphs
weighted graphs matching problems stable marriage
problem graph coloring paths and walks shortest
paths connectivity Eulerian and
Hamiltonian tours travelling salesman problem trees
spanning trees planar graphs Eulers formula
directed graphs strong connectivity relations
binary relations surjective and injective relations
symmetry, transitivity, reflexivity, equivalence of
relations posets and dags topological sort
3. Sums and asymptotics arithmetic, geometric and
power sums approximating sums harmonic sums products
stirlings approximation for finding factorial asymptotic
notations recurrences towers of
Hanoi solving recurrences master theorem linear
recurrences infinite sets countable and uncountable
sets cantors continuum hypothesis
4. Finite automata regular expressions pushdown
automata context free grammar pumping lemmas Turing
machines Church-Turing thesis decidability halting
problem reducibility recursion theorem time and
space measures complexity classes NP reductions
5. Probability events and probability spaces conditional
probability tree diagrams for computing probability
sum and product rules of probability A posteriori
probabilities identities of conditional probability
independence mutual independence birthday paradox
random variables indicator random variables probability
distribution functions Bernoulli, Uniform, Binomial
distributions Expectation linearity of expectations
sums of indicator random variables expectation of
products variance and standard deviation of random
variables Markovs and Chebyshevs theorems Bounds
for the sums of random variables random walks |
[1] Eric
Lehman, F Thomson Leighton, Albert R Meyer, Mathematics
for Computer Science, MIT, 2010
[2] Susanna S. Epp, Discrete Mathematics with Applications,
4th Edition, Brooks Cole, 2010
[3] Gary Chartrand, Ping Zhang, A First Course in Graph
Theory, Dover Publications, 2012
[4] Michael Sipser, Introduction to Theory of Computation,
2nd Edition, Cengage, 2012
|