🏠CS103

Course
Syllabus Honor Code
Readings
Mathematical Prerequisites (what you may assume is true) Guide to Elements and Subsets Guide to Proofs Guide to Set Theory Proofs Guide to $\LaTeX$ Guide to Office Hours Proofwriting Checklist How to Succeed in CS103 Guide to Negation Guide to Logic Translations Logic Translation Checklist Guide to Proofs on Discrete Structures Guide to Cantor's Theorem Discrete Structures Proofwriting Checklist Guide to Induction Induction Proofwriting Checklist Guide to the Subset Construction Guide to CFGs Guide to Self-Reference Guide to the Lava Diagram Timeline of CS103 Results
Lectures
0. 1/9 Introduction, Set Theory 1. 1/11 Mathematical Proofs 2. 1/13 Indirect Proofs 3. 1/18 Propositional Logic 4. 1/20 First-Order Logic, Part I 5. 1/23 First-Order Logic, Part II 6. 1/25 Functions, Part I 7. 1/27 Functions, Part II 8. 1/30 Functions, Part III 9. 2/1 Graphs, Part I 10. 2/3 Graphs, Part II 11. 2/6 Midterm Review 12. 2/8 Mathematical Induction, Part I 13. 2/10 Mathematical Induction, Part II 14. 2/13 Finite Automata, Part I 15. 2/15 Finite Automata, Part II 16. 2/17 Finite Automata, Part III 17. 2/22 Regular Expressions 18. 2/24 Nonregular Languages 19. 2/27 Context-Free Languages 20. 3/1 Turing Machines, Part I 21. 3/3 Turing Machines, Part II 22. 3/6 Turing Machines, Part III 23. 3/8 Unsolvable Problems, Part I 24. 3/10 Unsolvable Problems, Part II 25. 3/13 Complexity Theory, Part I 26. 3/15 Complexity Theory, Part II
Problem Sets
Guide to Partners
0. Problem Set 0 1. Problem Set 1 2. Problem Set 2 3. Problem Set 3 4. Problem Set 4 5. Problem Set 5 6. Problem Set 6 7. Problem Set 7 8. Problem Set 8 9. Problem Set 9
Exams
Preparing for the Midterm Practice Midterm 1 Practice Midterm 2 Practice Final Cumulative Practice Problems
Schedule

Complexity Theory, Part I

Monday March 13

Today we introduce complexity theory and the biggest unsolved problem in theoretical computer science: does P equal NP?

Links

Lecture Slides.pdf

All course materials © Stanford University 2022.
Website programming by Julie Zelenski with minor edits by Keith Schwarz. This page last updated 2023-Mar-14.