🏠CS103

Course
Syllabus Honor Code Office Hours Mathematical Prerequisites
Readings
Guide to Elements and Subsets Guide to Proofs 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 CFGs Guide to the Lava Diagram
Lectures
0. 6/26 Introduction, Set Theory 1. 6/28 Mathematical Proofs 2. 6/30 Indirect Proofs 3. 7/3 Propositional Logic 4. 7/5 First-Order Logic, Part I 5. 7/7 First-Order Logic, Part II 6. 7/10 Functions, Part I 7. 7/12 Functions, Part II 8. 7/14 Graphs, Part I 9. 7/17 Graphs, Part II 10. 7/19 Mathematical Induction, Part I 11. 7/21 Mathematical Induction, Part II 12. 7/24 Finite Automata, Part I 13. 7/26 Finite Automata, Part II 14. 7/31 Regular Expressions 15. 8/2 Nonregular Languages 16. 8/4 Context-Free Languages 17. 8/7 Turing Machines, Part I 18. 8/9 Turing Machines, Part II 19. 8/11 Unsolvable Problems 20. 8/14 Complexity Theory and P vs NP 21. 8/16 Final Review
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
Exams
Preparing for the Exams Practice Midterm 1 Practice Midterm 2 Midterm Extra Practice Problems Midterm Solutions Practice Final 1 Practice Final 2 Cumulative Practice Problems Final Exam Solutions
Schedule

Complexity Theory and P vs NP

Monday August 14

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-Aug-13.