Stanford CS103 Lecture 0: From Set Language to Cantor's Diagonal
Starting with elements, subsets, and power sets, this lecture culminates in Cantor's diagonal proof that no set is as large as its own power set.
#theory-of-computation
23 postsStanford CS103 Lecture 1: Building a First Direct Proof from Even and Odd
The even-square and odd-sum examples show how arbitrary choices, assumptions, witnesses, and a want-to-show become a checkable direct proof.
Stanford CS103 Lecture 2: Negation, Contraposition, and Contradiction
This lecture identifies exactly when an implication is false, then turns quantified negation, contraposition, and contradiction into checkable proof tools.
Stanford CS103 Lecture 3: Propositional Logic, Truth Tables, and Equivalence
Propositional logic abstracts English statements into Boolean variables, then uses truth tables to check connectives, translation direction, and equivalences.
Stanford CS103 Lecture 7: Functions II—Surjections, Assumptions, and Composition
This lecture uses surjections and a proof about birds to separate assuming from proving, then shows that involutions are injective and surjective and carries those ideas into function composition.
Stanford CS103 Lecture 8: Cardinality by Bijections and Cantor's Diagonal Argument
Two sets have equal cardinality when a bijection pairs their elements; Cantor's diagonal set defeats every function from S to its power set by constructing a value it misses.
Stanford CS103 Lecture 9: Graphs, Part I
This lecture moves from the formal definitions of graphs and digraphs to independent sets, vertex covers, and their complement relationship.
Stanford CS103 Lecture 13: Mathematical Induction, Part II
This lecture connects starting from ordinary induction to induction may start later, following the official examples and proof obligations.
Stanford CS103 Lecture 14: Finite Automata, Part I
This lecture connects why begin with a weak computer to from device behavior to a state machine, following the official examples and proof obligations.
Stanford CS103 Lecture 15: Finite Automata, Part II
This lecture connects the dfa definition connects the first half of cs103 to regular means that some dfa exists, following the official examples and proof obligations.
Stanford CS103 Lecture 16: Finite Automata, Part III
This lecture connects the automata ladder measures power with languages to dfa transition tables, following the official examples and proof obligations.
Stanford CS103 Lecture 17: Regular Expressions
This lecture connects from closure properties to a language syntax to regex is mathematics, not one library, following the official examples and proof obligations.
Stanford CS103 Lecture 18: Nonregular Languages
This lecture connects four equivalent descriptions of regularity to the precise finite-memory intuition, following the official examples and proof obligations.
Stanford CS103 Lecture 19: Context-Free Languages
This lecture connects from finite-state limits to recursion to the arithmetic grammar, following the official examples and proof obligations.
Stanford CS103 Lecture 20: Turing Machines, Part I
This lecture connects why the model changes after cfgs to long addition and local access, following the official examples and proof obligations.
Stanford CS103 Lecture 21: Turing Machines, Part II
This lecture connects the sample tm looks back from the end to beyond pairwise marking, following the official examples and proof obligations.
Stanford CS103 Lecture 22: Turing Machines, Part III
This lecture connects a quick quantifier audit for recognizers and deciders to why every decision problem can be represented as a language, following the official examples and proof obligations.
Stanford CS103 Lecture 23: Unsolvable Problems, Part I
This lecture connects returning from r, re, and utm to three self-reference warm-ups, following the official examples and proof obligations.
Stanford CS103 Lecture 24: Unsolvable Problems, Part II
This lecture connects defining and locating halt to why halt is recognizable, following the official examples and proof obligations.
Stanford CS103 Lecture 25: Unsolvable Problems, Part III
This lecture connects the lava diagram's two classification tasks to the deck's operational reading of rice's theorem, following the official examples and proof obligations.
Stanford CS103 Lecture 26: Complexity Theory
This lecture connects decidable does not mean feasible to efficiency requires choosing a resource, following the official examples and proof obligations.
Stanford CS103 Wrap-Up: Four Foundations and Where to Go Next
The final deck reconnects proofs, graphs, automata, and computability, then maps those foundations to Stanford courses that use them.
Stanford CS103: A Math Course Whose First Assignment Is Installing a C++ Compiler
CS103 teaches you how to write proofs, then teaches you what can't be proven — but the part nobody mentions is that it ships C++ programming assignments, starting with PS0: install Qt Creator. Its real asset is a shelf of homegrown 'Guide to X' handouts and a Proofwriting Checklist that graders actually deduct points against, all public. Solutions and practice exams sit behind Stanford login, and the Honor Code page explains why.