CSCI 361 - Fall 2025
Theory of Computation
Home | Lectures | Assignments | Resources | CS@Williams
Lectures
Readings will be assigned from the course textbook (Introduction to the Theory of Computation by Michael Sipser 3rd Ed). Copies of this textbook are reserved for loan at the Schow Library.
| Date | Topic | Reading | Daily Exercise |
|---|---|---|---|
| Sep 04 | 1. Introduction and Logistics | Handout | Sipser Ch 0 | Due Sept 9 |
| Sep 9 | 2. Finite Automata | Handout | Sipser Ch 1.1 | Due Sept 11 |
| Sep 11 | 3. NFAs | Sipser Ch 1.2 | Due Sept 16 |
| Sep 16 | 4. Regular Expressions | Sipser Ch 1.3 | Due Sept 18 |
| Sep 19 | 5. Myhill-Nerode Theorem | Handout | Due Sept 23 |
| Sep 23 | 6. Pumping Lemma | Sipser Ch 1.4 | Due Sept 25 |
| Sep 25 | 7. Context-free Languages | Sipser Ch 2.1 | Due Sep 30 |
| Sept 30 | 8. Push-down Automata | Sipser Ch 2.2 | N/A |
| Oct 2 | 9. Pumping Lemma for CFLs | Sipser Ch 2.3 | N/A |
| Oct 7 | Midterm 1 (In class) | Practice Exam | Solutions | N/A |
| Oct 9 | 10. Turing Machines | Sipser Ch 3.1 | Due Oct 16 |
| Oct 14 | No lecture (Reading Period) | N/A | N/A |
| Oct 16 | 11. TM Variants | Sipser Ch 3.2 | Due Oct 21 |
| Oct 21 | 12. Decidability & Diagonilization | Handout | Sipser Ch 4.1 & 4.2 | Due Oct 23 |
| Oct 23 | 13. Undecidability | Sipser Ch 5.1 | Due Oct 28 |
| Oct 28 | 14. Undecidability Reductions | Sipser Ch 5.1 | Due Oct 30 |
| Oct 30 | 15. Reductions using Computation History | Sipser Ch 5.2 | N/A |
| Nov 4 | 16. Wrap Up Computability & Review | Sipser 5.3 | N/A |
| Nov 6 | Midterm 2 (No Lecture) | Practice Midterm 2 | N/A |