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 Theory
 Sipser 5.3 & 7.1 Due Nov 11
Nov 6 Midterm 2 (No Lecture)
 Practice Midterm 2 Due Nov 11
Nov 11 17. Time Complexity
 Sipser Ch 7.2 Due Nov 13
Nov 13 18. NP Completeness
Sipser 7.4 Due Nov 18
Nov 18 19. More Reductions
Sipser 7.5 N/A
Nov 20 20. Wrapping NP hardness
Sipser 7.5 N/A
Nov 25 21. Time and Space Complexity
Sipser 8.1-8.2 N/A
Nov 27 No Lecture (Thanksgiving Break)
N/A
Dec 2 Advanced Topics
 N/A N/A
Dec 4 Wrap Up and Evals
Practice Final