CS103 Archive

This page contains archived versions of the Stanford CS103 (Mathematical Foundations of Computing) webpage in the quarters I've taught it. All internal links should be valid, though external links may no longer be functional.

2011-2012 Academic Year

Fall 2011

View the Fall 2011 CS103 website.

This was a quarter of firsts - my first quarter as a full-time lecturer at Stanford, my first time teaching CS103, and the first time teaching a class with over 200 students. I had a great time teaching and while the class had a few rough edges (as expected for a first iteration), I'm really psyched to teach it again.

Total students enrolled: 213
Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Graphs, Relations, Direct Proofs
- Week 2: Proofs by Contradiction and Contrapositive, Induction
- Week 3: Double Induction, Strong Induction, Propositional Logic
- Week 4: First-Order Logic, Functions, the Pigeonhole Principle, Trees
- Week 5: DFAs and NFAs
- Week 6: NFAs, Regular Expressions, the Pumping Lemma
- Week 7: Context-Free Grammars, Pushdown Automata, the Pumping Lemma for CFLs
- Week 8: Turing Machines, the Church-Turing Thesis, the Halting Problem, Properties of RE Languages
- Week 9: Reductions, Rice's Theorem, P, NP
- Week 10: NP-Completeness, Approximation Algorithms