From Set Language to Cantor's Diagonal | Stanford CS103 Lecture 0
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 postsBuilding a First Direct Proof from Even and Odd | Stanford CS103 Lecture 1
The even-square and odd-sum examples show how arbitrary choices, assumptions, witnesses, and a want-to-show become a checkable direct proof.
Negation, Contraposition, and Contradiction | Stanford CS103 Lecture 2
This lecture identifies exactly when an implication is false, then turns quantified negation, contraposition, and contradiction into checkable proof tools.
Propositional Logic, Truth Tables, and Equivalence | Stanford CS103 Lecture 3
Propositional logic abstracts English statements into Boolean variables, then uses truth tables to check connectives, translation direction, and equivalences.
Functions II—Surjections, Assumptions, and Composition | Stanford CS103 Lecture 7
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.
Cardinality by Bijections and Cantor's Diagonal Argument | Stanford CS103 Lecture 8
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.
Graphs, Part I | Stanford CS103 Lecture 9
This lecture moves from the formal definitions of graphs and digraphs to independent sets, vertex covers, and their complement relationship.
Mathematical Induction, Part II | Stanford CS103 Lecture 13
This lecture connects starting from ordinary induction to induction may start later, following the official examples and proof obligations.
Finite Automata, Part I | Stanford CS103 Lecture 14
This lecture connects why begin with a weak computer to from device behavior to a state machine, following the official examples and proof obligations.
Finite Automata, Part II | Stanford CS103 Lecture 15
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.
Finite Automata, Part III | Stanford CS103 Lecture 16
This lecture connects the automata ladder measures power with languages to dfa transition tables, following the official examples and proof obligations.
Regular Expressions | Stanford CS103 Lecture 17
This lecture connects from closure properties to a language syntax to regex is mathematics, not one library, following the official examples and proof obligations.
Nonregular Languages | Stanford CS103 Lecture 18
This lecture connects four equivalent descriptions of regularity to the precise finite-memory intuition, following the official examples and proof obligations.
Context-Free Languages | Stanford CS103 Lecture 19
This lecture connects from finite-state limits to recursion to the arithmetic grammar, following the official examples and proof obligations.
Turing Machines, Part I | Stanford CS103 Lecture 20
This lecture connects why the model changes after cfgs to long addition and local access, following the official examples and proof obligations.
Turing Machines, Part II | Stanford CS103 Lecture 21
This lecture connects the sample tm looks back from the end to beyond pairwise marking, following the official examples and proof obligations.
Turing Machines, Part III | Stanford CS103 Lecture 22
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.
Unsolvable Problems, Part I | Stanford CS103 Lecture 23
This lecture connects returning from r, re, and utm to three self-reference warm-ups, following the official examples and proof obligations.
Unsolvable Problems, Part II | Stanford CS103 Lecture 24
This lecture connects defining and locating halt to why halt is recognizable, following the official examples and proof obligations.
Unsolvable Problems, Part III | Stanford CS103 Lecture 25
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.
Complexity Theory | Stanford CS103 Lecture 26
This lecture connects decidable does not mean feasible to efficiency requires choosing a resource, following the official examples and proof obligations.
Wrap-Up: Four Foundations and Where to Go Next | Stanford CS103 Course Overview
The final deck reconnects proofs, graphs, automata, and computability, then maps those foundations to Stanford courses that use them.
Mathematical Foundations of Computing: How to Prove, Then What Can't Be Proven | Stanford CS103 Course Overview
CS103 is Stanford's mathematical foundations of computing course: the first half teaches proof writing through sets, logic, graphs and induction, and the second half covers finite automata, Turing machines, decidability and P vs NP. Slides, problem sets, starter files and the homegrown handouts are all public, and the autograded problems can be checked locally; solutions, practice exams and lecture recordings sit behind Stanford login.