CSCI 361 - Fall 2024

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 Reading HW
Sep 05 1. Introduction and Logistics
 Due Sept 10
Sep 10 2. Countability and DFA | Handout
 Sipser Ch 0, Barak Ch 1 Due Sept 12
Sep 12 3. Regular Languages | Handout
 Sipser Ch 1.1 & 1.2 Due Sept 17
Sep 17 4. Non-deterministic Finite Automata
 Sipser Ch 1.2 N/A
Sep 19 [Class Cancelled] 5. Regular Expressions
 Sipser Ch 1.3 N/A
Sep 24 6. Myhill-Nerode Theorem
 Handout Due Sept 26
Sep 26 7. Pumping Lemma
 Sipser Ch 1.4 Due Oct 1
Oct 1 8. Context-free Grammars
 Sipser Ch 2.1 Due Oct 3
Oct 3 9. Context-free Languages II
 Sipser Ch 2.2 Due Oct 8
Oct 8 10. Non-Context-Free Languages
 Sipser Ch 2.3 Due Oct 10
Oct 10 11. Turing Machines
 Sipser Ch 3.1 N/A
Oct 17 12. Turing Machines II
 Sipser Ch 3.2 & 3.3 N/A
Oct 22 Midterm (No class)
Oct 24 13. Decidable Languages
 Sipser Ch 4.1 Due Oct 29
Oct 29 14. Undecidability
 Sipser Ch 4.2 Due Oct 31
Oct 31 15. Mapping Reductions
 Sipser Ch 5.1 Due Nov 5
Nov 5 16. Reductions via Computation Histories
 Sipser Ch 5.2 N/A
Nov 7 17. Computability Theory Wrap Up
 Sipser Ch 7.1 Due Nov 12
Nov 12 18. Classes P and NP
 Sipser Ch 7.2 Due Nov 14
Nov 14 19. NP Completeness
 Sipser Ch 7.3 Due Nov 19
Nov 19 20. NP Completeness II
 Sipser Ch 7.5 Due Nov 21
Nov 21 21. Cook-Levin Theorem
Sipser 7.3
Nov 26 22. Wrap Up Complexity
N/A 1-Page Paper Due
Nov 28 No Lecture (Thanksgiving Break)
N/A
Dec 3 23. Wrap Up and Review
Study Guide
Dec 5 Student Presentations
N/A