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.

2016-2017 Academic Year

Spring 2017

This quarter's iteration of CS103 build on the version from Fall quarter. Thanks to the two buffer days in that syllabus, for the very first time I didn't need to cut out two full lectures' worth of material when putting this class together!

I decided to revert back to 180-minute midterms instead of in-class midterms, which I think worked much better. I'll continue that trend for the foreseeable future.

The major focus for this quarter was improving the quality of the grading feedback and generally pushing proofwriting much more than in previous quarters. The results were impressive: the quality of the work students submitted on the midterms and final exams were vastly superior to what we'd seen in previous quarters. I think the median student from this quarter is much better prepared to continue on to classes like CS161. Part of this was by more precisely articulating proofwriting style through a number of "proofwriting checklists" we distributed throughout the quarter, and part of this was by making the grading on the problem sets put a greater focus on proofwriting style.

There are a number of tweaks and updates that need to be made to this grading system, as is the case for any major overhaul. In the future we'll allocate more points toward intuition, and we'll try to be more aggressive about signaling why this level of rigor is so important. However, based on the results we're getting, I think that this new approach is far more effective at getting students to where they need to be.

I also made a number of more minor edits to the course, such as souping up the proofwriting on some of the earlier problem sets, recasting some of the older problem set questions to make them more applied, and cleaning up some of the lectures (especially on the Pigeonhole Principle). I think that trying to put in a proof of Sperner's lemma in the 2D case may have been a bit too ambitious, but other changes like exploring edge cases of self-reference and switching our proofs in computability to explicitly reference real program code were definite steps in the right direction.

- Total students enrolled:
**365** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Propositional and First-Order Logic
- Week 3: Binary Relations, Functions
- Week 4: Cardinality, Graphs, Pigeonhole Principle
- Week 5: Induction, DFAs
- Week 6: NFAs, Regular Languages
- Week 7: Regular Expressions, Nonregular Languages, CFGs
- Week 8: TMs, Church-Turing Thesis, Decidability, Recursion Theorem
- Week 9: Undecidability, Unrecognizability, Verifiers, P and NP
- Week 10: Reducibility, NP-Completeness, The Big Picture

Fall 2016

This quarter's offering of CS103 continued along the trajectory set in Fall 2015. I did more tuning and cleanup of the presentation of core concepts, ultimately devising a 28-lecture syllabus (with two lectures off on exam days) that will be easier to pick up and run with in future quarters. I decided to eliminate exploring non-RE languages via self-reference, primarily because the level of additional complexity required for introducing these concepts wasn't really worth the payoff. I also made some major adjustments to the presentation of the universal Turing machine, motivating it by starting with a computer-based TM simulator and thinking about how to recast it as a TM-based TM simulator and tying it in to virtualization. I was extremely happy with the presentation of undecidability, and really only think there are a few more bugs to work out, most of which are best accomplished in the problem sets (for example, requiring students to see why self-reference can't prove that every language is undecidable).

I made a number of pretty significant changes to the problem sets, ramping up the amount of proofs required and being more intentional with the topics covered. I think that I probably made them a bit too long, and will likely back that off a bit the next time I teach the class, but I did really enjoy working more advanced results and applications of the material into them.

I also introduced a number of new animated guides, including a Guide to Logic Negations, a Guide to First-Order Translations, a Guide to Elements and Subsets, and a Guide to Cantor's Theorem, most of which I built out over the summer. They seemed to work really well, and I'm hoping to soon take a crack at writing a Guide to Proofs on First-Order Logic. I'm also hoping to rewrite the existing (textual) Guide to Proofs to offer some more concrete details for students to focus on.

As an experiment, I tried having in-class midterms (80 minutes each). I think that this generally didn't go as well as the three-hour out-of-class midterms, though they were logistically much easier to administer. Next quarter, I'll likely back off from this idea, but I'm definitely open to revisiting it.

And of course, there were a ton of minor little tweaks scattered throughout the quarter. I tuned up the presentation on graphs and the pigeonhole principle and reworked the structure of the lectures on binary relations. I revisited the way I introduced the verifier-to-TM construction to make it more visual and added in more concrete visualizations of how to evaluate first-order logic formulas. I'm really happy with the slides and hope to continue using them in the future.

Making these changes took a lot of work, and I was definitely exhausted by the end of the quarter. But it seemed to pay off spectacularly - the course evaluations were higher than they've ever been. In Spring of this year I'm going to have a lot of tuning and updates to do, as always, but I'm optimistic about it.

- Total students enrolled:
**381** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Propositional and First-Order Logic
- Week 3: Binary Relations, Functions
- Week 4: Cardinality, Graphs
- Week 5: Induction, DFAs
- Week 6: NFAs, Regular Languages
- Week 7: Regular Expressions, Nonregular Languages, CFGs
- Week 8: TMs, Church-Turing Thesis, Decidability, Recursion Theorem
- Week 9: Undecidability, Unrecognizability, Verifiers, P and NP
- Week 10: Reducibility, NP-Completeness, The Big Picture

2015-2016 Academic Year

Winter 2016

This offering of CS103 - which, I think, was the most polished the class has been to date - was essentially the Fall 2015 version with a ton of cleanup and two whole lectures (!!) of content removed to accommodate the Winter schedule. With the lessons learned from Fall 2015, I managed to significantly tighten up the presentation of TMs (scaling down the intellectual burden involved with subroutines, for example) and come up with a much better lecture on complete induction (thanks, trees!). I've also made a ton of notes to myself with areas for future improvement, mostly with regards to moving motivations earlier into lecture and trying to take some of the more theory-heavy topics and replace them with more practical applications.

This quarter, I introduced the Guide to Self-Reference and Guide to the Lava Diagram, two animated slide decks walking through the intuition for two of the trickiest topics from the quarter. They were very well-received and I'm extremely proud of how well they turned out. I think they really worked - people did a lot better on the final exam questions on computability than they've historically done in the past. I'm hoping to expand these guides throughout the quarter and rework some of the supporting handouts from throughout the quarter to use this new format.

There's still a lot of work to be done to get this class into a good working order. I need to figure out a better way to design exams that communicate our expectations. I need to find some way to integrate more of the topics from the discrete math section into the computability/complexity topics. I also need to find a way to cut even more material, since we're still totally overloaded with material. That said, this version of the class got some of the highest reviews CS103 has ever received, so there's still a lot to be really happy about!

- Total students enrolled:
**382** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Propositional and First-Order Logic
- Week 3: Functions, Cardinality
- Week 4: Relations, Graphs
- Week 5: Induction, DFAs
- Week 6: NFAs, Regular Languages
- Week 7: Regular Expressions, Nonregular Languages, CFGs
- Week 8: TMs, Church-Turing Thesis, Decidability, Recursion Theorem
- Week 9: Undecidability, Unrecognizability, Verifiers, P and NP
- Week 10: Reducibility, NP-Completeness, The Big Picture

Fall 2015

This offering of CS103 started with a pretty serious overhaul of the first half of the class. I moved first-order logic to the second week and gave an entire problem set pretty much devoted to first-order and propositional logic. Using that as a starting point, I increased the treatment of discrete mathematics and spent a lot more time in class going over how to use first-order logic as a tool for reasoning about proofs. I added in a new problem set about graphs, and pushed induction to the end of the section on discrete structures rather than the beginning. The net result seems to be that people got a much better treatment of discrete math and had much better outcomes with proofwriting and formal definitions.

To fit all this in, I used the two extra lectures that come with a fall quarter class. I also removed nondeterministic TMs from the CS103 lineup, which freed up about half a lecture from the section on Turing machines and another half lecture from the portion on P and NP. I also lowered my expectations about student outcomes with P versus NP, since they'll get a more in-depth treatment of the subject in CS161 (and CS154, if they choose to take it).

I also for the first time introduced a series of challenge problems throughout the quarter for students interested in more of a challenge. I'm really happy with the first set of challenge problems (which lead up to a proof about the chromatic number of the rational plane) and pretty happy with the other two. I hope to keep using them in the future.

As promised, I also introduced a ton of new handouts. It's unclear how effective they were, though I did find an unusual trend in the grades: freshman in CS103 this quarter did substantially better than every other group. I'm wondering if this is because the freshmen were actually going through all the materials, or whether this is due to other effects.

The overhaul required a ton of effort, and I'm really hoping that next quarter will be more relaxing. I know that I need to tune up
my presentation of TM subroutines (which, right now, are terrifying), my coverage of complete induction (I still have never really
gotten that one to work right), and my coverage of P versus NP (which right now, I think, is a bit *too* high level). I also
will need to figure out how to cut a lecture for winter quarter (one bonus lecture on Eulerian graphs is easy to eliminate). I've
taken tons of notes on my materials for next time, so hopefully I'm closing in on a stable, final version of this class!

- Total students enrolled:
**275** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Propositional and First-Order Logic
- Week 3: Relations, Functions
- Week 4: Cardinality, Graphs
- Week 5: Induction, DFAs
- Week 6: NFAs, Regular Languages, Regular Expressions
- Week 7: Nonregular Languages, CFGs, Turing Machines
- Week 8: Church-Turing Thesis, Decidability, Recursion Theorem
- Week 9: Undecidability, Unrecognizability, Verifiers, P and NP
- Week 10: Reducibility, NP-Completeness, The Big Picture

2014-2015 Academic Year

Spring 2015

I was very pleased with how this iteration of CS103 worked out. I ended up continuing to use the recursion theorem as a primary mechanism for showing undecidability and unrecognizability, but significantly overhauled the presentation to focus more on actual source code than on high-level descriptions. This cleaned up much of the presentation and made it much easier for students to see how these constructions worked. I also reordered the treatment of verifiers and NTMs to put verifiers earlier, then heavily push verifiers as a mechanism for understanding RE. This made a lot of the proofs easier to understand and replaced complicated nuances of recognizers for simpler (though still tough) notions of verification.

This quarter also marked a return to an older model where I covered first-order logic prior to discussing graphs, binary relations, and functions, which I believe helped out quite a bit. There is still a lot more work to be done integrating first-order logic into the discrete structures porition of the course - specifically, I need to do a much better job talking about how to write proofs that call back to formal definitions - but I think it made it easier to define complex concepts more precisely.

Finally, this quarter marked the first iteration of CS103A, an add-on course providing extra review and problem-solving practice. That class went pretty well for a first offering, and I'm hoping to tune it a lot more precisely in the future.

Next time I teach this course, I'm going to improve in a few specific areas. First, I need to do a better job teaching students how to manipulate first-order definitions and how to use them to guide the basic structure of mathematical proofs. That's going to be a bit tough, especially given that we're already packed to the gills with material. Second, I need to update my presentation of P and NP, probably by cutting out the NTM intuition for NP and focusing more on reducibility and verification. Finally, I need to provide more support materials along the way, either by fleshing out the course reader, building a more supplementary handouts, or some combinatino of both. That said, this was, in my opinion, easily the best offering of CS103 to date, and I'm quite happy with how the class looks now.

- Total students enrolled:
**329** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Induction, Propostional Logic
- Week 3: First-Order Logic, Graphs
- Week 4: Functions, Cardinality, Relations
- Week 5: DFAs, NFAs, Regular Languages
- Week 6: Regular Expressions, Myhill-Nerode Theorem, CFGs
- Week 7: Turing Machines, The Church-Turing Thesis, The Recursion Theorem
- Week 8: Undecidability, Verifiers, Unrecognizability
- Week 9:
**P**,**NP**, Reducibility - Week 10:
**NP**-Completeness, The Big Picture

Fall 2014

This was my sixth offering of CS103. I ended up making a lot of changes since the prior offering. Students were
allowed to work on problem sets in pairs and triples, which helped students get more practice writing proofs
and significantly cut down on the TA grading load. I started offering in-person practice midterms, leading to
much better exam performances overall. I also changed the discussion of computability quite significantly
by focusing on the recursion theorem as a method for showing impossibility results and exploring equivalent
definitions of the class **RE** through verifiers. I think that I'm on to something with this setup but that
it needs a bit more tuning, so we'll see how it goes next time around. (Oh, and this class broke the CS103 size
record by about 80 students!)

- Total students enrolled:
**412** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Induction, Graphs
- Week 3: Graphs, Relations, Functions
- Week 4: Cardinality, Logic
- Week 5: Logic, DFAs, NFAs
- Week 6: Regular Expressions, Myhill-Nerode Theorem, CFGs
- Week 7: Turing Machines, The Church-Turing Thesis
- Week 8: Unrecognizablility, Undecidability, The Recursion Theorem
- Week 9: co-Recognizability,
**P**,**NP** - Week 10:
**P**vs.**NP**,**NP**-Completeness, The Big Picture

2013-2014 Academic Year

Fall 2013

This fifth offering of CS103 broke the size record by quite a large margin (333 students!). I made a lot of changes to the course that really seemed to pay off. I updated the treatment of discrete math to stress discrete structures more than in past quarters and, accordingly, revised some of the problem sets. I also replaced the pumping lemma with the Myhill-Nerode theorem, which made for a much more intuitive presentation of nonregular languages and led to some much cooler problem set questions. I revised all the discussion problems to be more relevant, gave out more practice problems, and dedicated a few minutes of lecture time each day to answering questions students asked via Google Moderator. CS103 got its highest evaluations ever and was one of the highest-rated courses in the entire School of Engineering, and I'm extremely happy with how it turned out. That said, I've got a lot of ideas I want to test out next time, so I'm looking forward to the next time I get to teach it!

- Total students enrolled:
**333** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Induction, Graphs
- Week 3: Graphs, Relations, Functions
- Week 4: Cardinality, Logic
- Week 5: Logic, DFAs, NFAs
- Week 6: Regular Expressions, Myhill-Nerode Theorem, CFGs
- Week 7: Turing Machines, The Church-Turing Thesis
- Week 8: Unrecognizablility, Undecidability, co-Recognizability
- Week 9: Mapping Reductions,
**P**,**NP** - Week 10:
**P**vs.**NP**,**NP**-Completeness, The Big Picture

2012-2013 Academic Year

Winter 2012-2013

This fourth offering of CS103 was the largest offering I'd taught so far (with 265 students!) I was extremely happy with how the material worked out this time - the coverage of Turing machines was a lot more focused, and more generally the intuitions seemed to shine through marvelously. We also added in a new Regular Expression design tool (thanks, Remington!) that made it possible to test regular expressions in more depth. I am very much looking forward to the next iteration of CS103, when I think that I'll finally have all the bugs ironed out!

- Total students enrolled:
**265** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Induction, Graphs, Relations
- Week 3: Functions, Cardinality, Diagonalization, the Pigeonhole Principle
- Week 4: Propositional Logic, First-Order Logic, SAT Solving
- Week 5: DFAs, NFAs, and Regular Expressions
- Week 6: The Pumping Lemma, CFGs, PDAs
- Week 7: Turing Machines, The Church-Turing Thesis
- Week 8: Unrecognizablility, Undecidability, co-Recognizability
- Week 9: Mapping Reductions,
**P**,**NP** - Week 10:
**P**vs.**NP**,**NP**-Completeness, The Big Picture

Fall 2012

This was the third time I taught CS103. This quarter marked the introduction of the Theorem and Defintion reference, a set of course notes for the first few weeks, and an automatic grade reporting tool. I'm very happy with how the quarter turned out, and I'm really psyched to build off of it for the upcoming Winter quarter!

- Total students enrolled:
**185** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Proof Techniques
- Week 2: Induction, Graphs, Equivalence Relations
- Week 3: Order Relations, Functions, Cardinality, the Pigeonhole Principle
- Week 4: Propositional Logic, First-Order Logic, SAT Solving
- Week 5: DFAs and NFAs
- Week 6: Regular Expressions, The Pumping Lemma, CFGs, PDAs
- Week 7: Turing Machines, Programming Turing Machines, R and RE Languages
- Week 8: Unsolvable Problems, Mapping Reductions, co-RE
- Week 9: P, NP, NP-Completeness
- Week 10: NP-Completeness, Approximation Algorithms, Cryptography, The Big Picture

2011-2012 Academic Year

Spring 2012

The second offering of CS103 was a lot more polished than the first run. I wrote a set of course notes for the first week of the course, and significantly tightened up the treatment of proof techniques and reductions. I am very happy with how this offering of the class turned out, and I'm very excited to see how well it will go when I teach it this Fall!

- Total students enrolled:
**181** - Lecture Topics:
- Week 1: Set Theory, Cantor's Theorem, Direct Proofs, Indirect Proofs
- Week 2: Induction, Graphs, Relations
- Week 3: Functions, the Pigeonhole Principle, Propositional Logic
- Week 4: First-Order Logic, SAT Solving, DFAs
- Week 5: NFAs, Regular Expressions, the Pumping Lemma
- Week 6: Context-Free Grammars, Pushdown Automata, Turing Machines
- Week 7: The Church-Turing Thesis, Universal TMs, Unsolvable Problems
- Week 8: Reductions, P
- Week 9: NP, NP-Completeness
- Week 10: Approximation Algorithms, The Big Picture

Fall 2011

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