🏠CS103

Course
Syllabus Honor Code Mathematical Prerequisites Office Hours How to Improve
Resources
Guide to Elements and Subsets Guide to Proofs Guide to Proofs on Sets Guide to $\LaTeX$ Proofwriting Checklist Guide to Negation Guide to Logic Translations Logic Translation Checklist Guide to Proofs on Discrete Structures 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/8 Introduction, Set Theory 1. 1/10 Mathematical Proofs 2. 1/12 Indirect Proofs 3. 1/17 Propositional Logic 4. 1/19 First-Order Logic, Part I 5. 1/22 First-Order Logic, Part II 6. 1/24 Functions, Part I 7. 1/26 Functions, Part II 8. 1/29 Graphs, Part I 9. 1/31 Graphs, Part II 10. 2/2 Graphs, Part III 11. 2/5 Midterm Review 12. 2/7 Mathematical Induction, Part I 13. 2/9 Mathematical Induction, Part II 14. 2/12 Finite Automata, Part I 15. 2/14 Finite Automata, Part II 16. 2/16 Finite Automata, Part III 17. 2/21 Regular Expressions 18. 2/23 Nonregular Languages 19. 2/26 Context-Free Languages 20. 2/28 Turing Machines, Part I 21. 3/1 Turing Machines, Part II 22. 3/4 Turing Machines, Part III 23. 3/6 Unsolvable Problems, Part I 24. 3/8 Unsolvable Problems, Part II 25. 3/11 Complexity Theory, Part I 26. 3/13 Complexity Theory, Part II 27. 3/15 Where to Go from Here
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
Exam Logistics
Midterm 1 Practice Exam 1 Midterm 1 Practice Exam 2 Extra Practice Problems 1 Midterm 1 Solutions Midterm 2 Practice Exam 1 Midterm 2 Practice Exam 2 Extra Practice Problems 2 Midterm 2 Solutions Cumulative Practice Problems Final Practice Exam 1 Final Practice Exam 2 Final Exam Solutions
Schedule

Complexity Theory, Part I

Monday March 11

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

Links

Condensed Slides.pdf
Lecture Slides.pdf

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