Course Schedule
The following is the planned schedule for the course. Assignments and due dates are subject to change, so be sure to attend class so you don't miss any important announcements.
Here is a short guide on how to get help when you're stuck.
Assignments
| Week | Topic | Reading | Assignment Due |
|---|---|---|---|
| 0 | Course Introduction | Lecture Notes, Syllabus, Policies | C++ Coding Setup |
| 1 | Algebra Review, Set Theory, Cantor's Theorem | Lecture Notes 1, 2, and 3, Dispute over Infinity | Computational Math |
| 2 | Direct Proofs | Lecture Notes 4, 5 | Proof Problems 1 |
| 3 | Indirect Proofs | Lecture Notes 6, 7 | Computational Logic |
| 4 | First Order Logic | Lecture Notes 8, 9, 10 | Proof Problems 2 |
| 5 | Graph Theory, Binary Relations, Functions | Lecture Notes 11, 12, 13, Sipser Ch. 0 | Midterm 1 |
| 6 | Finite Automata | Lecture Notes 14, 15, Sipser Ch. 1.1 - 1.2 | - |
| 7 | Regular Expressions and Nonregular Languages | Lecture Notes 16, 17, Sipser Ch. 1.3 - 1.4 | State Machine |
| 8 | Context-Free Languages | Lecture Notes 19, 20, Sipser Ch. 2.1 | - |
| 9 | SPRING BREAK | Sipser Ch 3 | - |
| 10 | Turing Machines, Church-Turing Thesis | Lecture Notes 21 | Midterm 2 |
| 11 | Decidability and Reducibility | Lecture Notes 22, 23, 24, Sipser Ch 4 and 5 | Turing Machine |
| 12 | Time Complexity | Lecture Notes 25, 26 Sipser Ch 7 | - |
| 13 | Intractability | Lecture Notes 27, Sipser Ch 8 | Computational Problem Classifier |
| 14 | Survey of Advanced Topics | Lecture Notes, Sipser Ch 6, and 10 | - |
| 15 | Review for Final | - | - |
Weekly Assignemnts
Unless otherwise specified, weekly assignments are due by Saturday night at 11:30 PM.
Attribution
These slides are for instructional use only. Many of the concepts and treatment of those concepts for weeks 0 - 5 come from the CS103 Mathematical Foundations of Computing course at Stanford.
Unless otherwise attributed, images in the slides probably came from the Sipser text or Wikipedia.