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.

2019-2020 Academic Year

Fall 2019

This quarter was motivated by the maxim that elegance is not when there's nothing left to add, but when there's nothing left to take away. I decided to take a close look at the topic coverage for the course and the problem sets with that question in mind, and the result was a version of CS103 that, I think, is quite beautiful but more focused.

The most notable change from the Fall 2018 version of CS103 was a reduction in the sizes of the problem sets. I took a hard look at the problem sets from last quarter with the goal of (1) preserving the long-running threads that made for interesting questions and (2) reducing their size as much as possible without sacrificing coverage. These goals are in tension with one another, but I think I managed to find a good compromise between them. This meant, sadly, cutting the star-drawing questions from the Fall 2018 offering. As beautiful as they were, students didn't seem to warm to them as much as I'd hoped, and their introduction expanded the topic coverage of the quarter to include number theory in a way that competed with other topics for understanding. We also lost another beautiful question, the one about the universal set, which I removed because I couldn't find a way to fit it in with everything else that needed to be covered.

What remained, however, seemed much more polished than before. In addition to the above changes, I redesigned some of the existing questions to have a more exploratory workflow. Many questions are now structured in a way that has students first engage with a new topic by playing around with concrete examples before jumping into a more abstract, proof-based setting. This seemed to go really well, leading students to have much better handles on the topics we did end up keeping. I also was able to retain the hypercube and Myhill-Nerode theorem threads, which helped tie the topics together nicely.

Another huge change to the problem sets was the introduction of first-order logic and propositional logic autograders. This led to every single logic problem on Problem Set 2 being autograded, saving a huge amount of TA time and improving student understanding. I had to restructure / change some of the older logic translation and logic negation questions, but I managed to do so in a way that preserved much of the underlying mathematical structure. (For a fun exercise, see if you can find the correspondences between the old and new problems!) More generally, I upgraded the autograder infrastructure to provide better error-reporting and to handle missing files more gracefully, something that saved a lot of frustration on the students' parts. There's still some work to do in improving autograder quality, but I think this was a huge win overall.

On the lecture side, I ended up dropping coverage of Hasse diagrams and of graph coloring. I was sad to see them go - they're wonderful concepts - but nothing really ended up depending on them and cutting them out freed up more time to explore the other concepts in more depth. Surprisingly, cutting these topics didn't mean that lectures got out early; rather, we ended up taking more time talking about the other concepts as a group, which I think led to better overall understanding of the remaining topics.

Also on the lecture side, I did a pretty sigificant overhaul of the introductory lecture on mathematical proofs, framing proofwriting in terms of a "Proof Triangle" combining definitions, intuitions, and conventions. This lecture also spent a lot of time focusing on problem-solving as a distinct activity than proofwriting, something that normally we'd lumped together. I think this went over well with students, and I'm planning on keeping this up in the future. I also made more localized improvements to the very first lecture on set theory and to the lectures on first-order logic that I'm quite happy with. Additionally, I factored out the discussion of the subset construction from our lecture on automata into its own "Guide to the Subset Construction," which decompressed the lecture and made for a nice, standalone resource for students. I was surprised to see that many of the lectures I had previously considered to be in great shape - the first lectures on automata, the second lecture on induction, etc. - now are some of the weaker lectures! I suppose that's a good thing - it means that I've improved the average quality of the lectures significantly since they got into a stable form.

I think there's still quite a lot of work to do to get things into a state of final polish. The slimmed-down problem sets included some new problems that could use some tuning and focus. The course has generally drifted more and more toward the theory side of things and away from some of the practical motivating questions that it used to explore, and perhaps it's worth resurrecting some older problem set questions that were more application-driven. The lectures are still very much in need of tuning and correction, and I imagine there are even more topics that we could eliminate from the course.

Something I'll need to work on on the future - the DFA/NFA editor and other online tools are starting to show their age a bit, in that they don't directly interface with GradeScope in the same way as the other "coding"-style assignments. It may be worth rewriting these systems so that they hook right into the GradeScope autograding infrastructure. This would make it possible for students to test and iterate, likely leading to much better outcomes.

That being said, this quarter's offering of CS103 had some of the highest reviews ever in terms of instructional quality and course organization, which means that in many ways the changes I made here were very much steps in the right direction!

- Total students enrolled:
**266** - 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
- Week 6: DFAs, NFAs, Regular Languages
- Week 7: Regular Expressions, Nonregular Languages, CFGs
- Week 8: Turing Machines
- Week 9: Universal TM, Recognizability/Decidability, Recursion Theorem, Undecidability, Unrecognizability, Verifiers
- Week 10: P and NP, Reducibility, NP-Completeness, The Big Picture

2018-2019 Academic Year

Fall 2018

This quarter's offering of CS103 represents one of the largest changes to the problem sets since Fall 2015. There are too many specific changes to list here, but the major goals were to (1) integrate proofwriting more tightly into the back half of CS103, (2) to increase the number of long-running threads across the problem sets, and (3) to select problems that had "stakes" on them along the lines of my new CS106B assignments. In many ways, I think these problem sets met those goals. I introduced a chain of questions in the back half of the problem sets that culminated in a formal proof of the full version of the Myhill-Nerode theorem, tying equivalence relations, functions, and induction into the material on regular languages in ways we previously hadn't been able to make work. This was one of three long-running threads added into the problem sets - another was on star-drawing (exploring number theory), and a third was on hypercubes and symmetries (exploring group theory). I think that these problems will need some tuning to get right in future offerings, but I very much think they're a huge step in the right direction. I'm not sure how well I hit goal (3) - I'll go and update this section after getting the course evaluations to see what people thought.

I also piloted a number of changes to the introductory lectures and supporting materials. I retired the old "Guide to Proofs," which didn't seem to be as effective as the Proofwriting Checklist, and added in a new Guide to Proofs on Set Theory that seemed to dramatically improve student outcomes in that area. I also cut out our treatment of rational and irrational numbers, which had always felt a little bit shoehorned into the course. I revamped Problem Set One to introduce more practice with proof reading in addition to proof writing, which seemed to be effective, and changed the problem set grading system by adding in a square root normalization term at the end, something shamelessly stolen from MIT which Cynthia piloted last quarter.

Additionally, I just generally spruced up some of the problem sets that hadn't been touched in a while. I replaced many of the classic DFA and regex design questions with newer ones that had a bit more of a practical feel to them. I decided to remove the lengthy treatment of strict weak orders from Problem Set Three, which hadn't turned out as well as I'd hoped when I introduced it last year, and added in new questions about linear orders and group preferences. (There's still a question on strict weak orders that's much more polished and focused than last year's version; it turned out pretty well!)

On the backend, I upgraded the assignment autograders to use a newer, more robust system that can recover from crashes and timeouts in ways the previous system wasn't capable of handling. I still need to do some more work on it to pass back information about compiler errors, something that came up multiple times this quarter.

The most serious software upgrade I introduced was an interactive Problem Set Zero that guides students through an introduction to star-drawing, setting up one of the long threads for the problem sets. This seemed to go over well, and I'm going to need to think about whether it'll be possible to use this in other contexts. Could we use this to teach first-order logic? Binary relations? There's a lot of options here and I'll likely spend some time over one of the breaks playing around with this.

The other major shift in this iteration of CS103 was increasing the focus on intuition and conceptual understanding. In previous offerings of CS103, a common student concern was that they were having trouble demonstrating what they knew to be true through mathematical proofs. I decided to add in more questions that explored concepts in ways that didn't involve proofwriting, such as an exploration of permutations and permutation composition through dancers changing positions and a question on how to think about automorphisms as symmetries. The second exam also included several questions that explicitly pushed on conceptual understanding, and it seemed to be well-received. I'm going to try to keep this up in the future.

Most of the lectures this quarter were unmodified from previous quarters or represented small incremental improvements to older versions. One major change was a new in-class "MathematiCalisthenics" exercise to motivate complete induction, which seemed to go over well. Another was a revised presentation of undecidability via self-reference using self-defeating objects. I think the initial version of this updated lecture went well but could use a little bit of tuning in the future. I swapped out one of the examples in the lecture on the pigeonhole principle for an example of a little logic / math problem with a gorgeous solution; that one seemed to go over very well. The last major upgrade was a new presentation of NP-hardness and NP-completeness that I think went over much better with students than the usual one.

On the staffing side, this quarter was the first in a long while with no returning TAs, so the start of the quarter was busier than usual with extra staff training sessions. I also updated all of the internal documentation for the TAs, which turned out to be in need of some touch-ups.

At the end of this quarter I have a lot of items on my to-do lists for the future. The problem sets we gave out this quarter will need some more tuning to get into ideal shape, and I'm going to see whether I can pare them down a bit without sacrificing (much?) coverage. I'm starting to think that my treatment of P and NP is in dire need of an upgrade; given that the goal is to cover the P versus NP question in two lectures (!), I suspect that what I'm doing isn't as effective as it could be. I have some ideas about how to revisit this (including the radical idea of defining NP as "problems that reduce to SAT in polynomial time" and then introducing Cook-Levin as "a problem is in NP if and only if there's a polynomial-time verifier for it," reversing the usual ordering). In the course of researching topics for the second midterm, I came across a ton of beautiful concepts in graph theory that seem more interesting and exciting than what we're doing now - I'll need to see whether that can be worked into the main body of the class. And more generally, I'm going to take a hard look to see whether there are ways to scale back the breadth of content a bit. Removing rational and irrational numbers and offloading some of the nuances of set theory proofs into a separate handout made the lectures way less hectic and improved students outcomes; are there any other topics (looking at you, planar graphs and graph coloring) that could also be removed without doing much damage?

The more systemic areas to focus on in the future are going to be the shape of CS103A and the sorts of support resources afforded to students. Currently, CS103A functions mostly as unstructured problem-solving time. Would it be better to do problems as a group to show off a particular problem-solving modality? Right now, the CS103 problem set solutions just include polished answers. Should they also include advice about how to think about those problems, so that students see that the proof is just an artifact at the end of a line of reasoning? Right now, we have more office hours time slots than the LaIR provides for CS106A/B, and yet students feel like they can't get time of day with the TAs. Should we introduce discussion sections, or change up the format of how our office hours work? Julie had the great suggestion of asking for an extra TA to meet one-on-one regularly with students who are struggling the most - what would that look like? I don't yet have answers to these questions, and fortunately I've got some time to think them over before I jump into the next iteration of this class.

I'm going to update this once I hear back from students in their course evaluations, but from our perspective it seems as though students did much better this quarter than in previous offerings of CS103. The problem set scores and exam scores were higher on exams that I didn't think were any easier than what we've given in the past, and that's including the fact that most of the problem sets were revised from scratch. I'm going to have to dive deeper into this to see if I can figure out what exactly is causing students to do better - whatever it is, I'm going to want to keep it up!

- Total students enrolled:
**284** - 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
- Week 6: DFAs, NFAs, Regular Languages
- Week 7: Regular Expressions, Nonregular Languages, CFGs
- Week 8: TMs (smoky conditions canceled one lecture)
- Week 9: Universal TM, Recognizability/Decidability, Recursion Theorem, Undecidability, Unrecognizability, Verifiers
- Week 10: P and NP, Reducibility, NP-Completeness, The Big Picture

2017-2018 Academic Year

Winter 2018

This was my first time ever co-teaching a major class! A huge thanks to Cynthia Lee for all her input and advice over the course of this quarter.

With Cynthia on board, we significantly overhauled the lectures, dropping the "Your Questions" section in favor of smaller, in-class questions taught using peer instruction. These questions seemed to be quite effective at getting students to think about the concepts we were teaching and to help them get a better sense for key terms and definitions.

In other ways, this offering of CS103 served as a refinement of the version from Fall quarter. We patched up some rough edges around the new problem sets and added in a few new problems to some of the problem sets to address weaknesses we'd seen on the final exam from Fall 2017. We introduced some new materials (a "Guide to Proofs on Discrete Structures" and a "Discrete Structures Proofwriting Checklist," which have been badly needed for a long time). We also made some changes to our grading system, the first time we've done so in a while, and I'm quite happy with how they turned out.

Another visible change is the addition of more structured hints and advice throughout the problem sets. On many problems, especially at the start of the quarter, we provided students hints that, rather than just telling students how to crack each problem, talked about a general mentality or skill the student could use to approach similar problems in the future. We were quite happy with the results!

Co-teaching this class gave me the opportunity to sit in the audience and watch this class be taught for the first time, and in my conversations with Cynthia we came up with some beautiful new intuitions and insights that I hope we feed back into the course in future offerings. One topic I'm particularly excited to explore is the idea of framing self-reference proofs in terms of self-defeating objects: a decider for the halting problem can't exist because it can be used against itself, just as there can't be a largest integer because it could be used to show that there's an even larger integer.

Although I'm very happy with how the in-class questions worked out, I'm a little bummed that we had to cut the popular "Your Questions" sections from each class in order to make it work. Given how much material there is packed into this course I'm not sure there's a way to get the two to work side-by-side, but this is something I'd like to try to address for future quarters.

- Total students enrolled:
**292** - 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 2017

This quarter's offering of CS103 introduced a number of pretty significant changes. The most visible was the inclusion of new programming assignments as part of PS1 - PS5. These coding assignments were designed to get students to take the higher-level mathematical constructs we've learned and to express them precisely in code in a way that the computer could understand. For example, on Problem Set 1, the assignment asks students to write code for predicates on sets to check whether, say, S is a subset of T, whether S = {T}, etc. These assignments were popular with students and we saw some positive results. We didn't, for example, see anyone mix up element-of and subset-of after the first problem set!

Independently of the new coding assignments, I also made some pretty serious changes to the early problem sets, especially Problem Set Three, by swapping out some of the more abstract problems for questions about how strict orders and equivalence relations make an appearance in the C++ standard library.

The other major area I made changes this quarter was in the messaging around grades and progress. Students are always a little shocked at the grades they get on the first few problem sets of the quarter, since that's when they're still getting used to writing proofs. I decided to change the lectures to spend much more time talking about the grade distribution and to frame the message as "there's always room for improvement" and "you are on an upward trajectory." I similarly sent out custom emails to each student around the first and second midterm congratulating people who had done well and reassuring people who didn't perform as well as they'd liked. I also made sure to call attention to the progress students had made over the course of the quarter.

- Total students enrolled:
**320** - 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

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