🏠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. 4/4 Introduction, Set Theory 1. 4/6 Mathematical Proofs 2. 4/8 Indirect Proofs 3. 4/11 Propositional Logic 4. 4/13 First-Order Logic, Part I 5. 4/15 First-Order Logic, Part II 6. 4/18 Functions, Part I 7. 4/20 Functions, Part II 8. 4/22 Functions, Part III 9. 4/25 Graphs, Part I 10. 4/27 Graphs, Part II 11. 4/29 Mathematical Induction, Part I 13. 5/4 Mathematical Induction, Part II 14. 5/6 Finite Automata, Part I 15. 5/9 Finite Automata, Part II 16. 5/11 Finite Automata, Part III 17. 5/13 Regular Expressions 18. 5/16 Nonregular Languages 19. 5/18 Context-Free Languages 20. 5/20 Turing Machines, Part I 21. 5/23 Midterm 2 Review 22. 5/25 Turing Machines, Part II 23. 5/27 Turing Machines, Part III 24. 6/1 Unsolvable Problems, Part I 25. 6/3 Unsolvable Problems, Part II 26. 6/6 Complexity Theory and P vs NP 27. 6/8 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
Preparing for the Midterm Practice Midterm 1 Practice Midterm 2 Practice Final Cumulative Practice Problems
Schedule

Complexity Theory and P vs NP

Tuesday June 6

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-Jun-04.