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 – russell’s paradox – well-ordering principle – induction – invariants – strong induction – structural induction – pigion hole principle – parity – number theory – divisibility – gcd – euclid’s 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 – Euler’s 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 – stirling’s approximation for finding factorial – asymptotic notations – recurrences – towers of Hanoi – solving recurrences – master theorem – linear recurrences – infinite sets – countable and uncountable sets – cantor’s 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 – Markov’s and Chebyshev’s theorems – Bounds for the sums of random variables – random walks