The following outline is based on what I did the last time I taught this course. This time may differ. I will try to update this page as we go along ...

• Topics

  • Sets and functions.

  • Counting - permutations and combinations, inclusion-exclusion, Pascal's triangle and the binomial theorem.

  • Infinite sets. Countability and uncountability. Hilbert's hotel.

  • Number theory - Euclidean algorithm, fundamental theorem of arithmetic, Fermat's (little) theorem, modular arithmetic, fast exponentiation, public key cryptography.

  • Geometric series. Fermat and and Mersenne primes.

  • Induction, strong induction, structural induction. Inductive definitions. Ackerman's function. Trees.

  • Graphs. Taxonomy (simple, directed, connected, ...). Examples: K(n), K(m,n), C(n), W(n), Q(n). Paths and the adjacency matrix. Trees, components, Euler and Hamiltonian paths and circuits. Planarity, Euler's formula, Platonic polyhedra.

• Metatopics

  • Everyday logic. Contrapositive and converse. Examples and counterexamples.

  • Work out special cases to understand general theorems. Look for patterns.

  • Proofs are narratives, not strings of symbols (with apologies to the formal logicians). Learn to write more.

  • Digress to learn interesting things that aren't necessarily part of the curriculum or tested on the exams.