This calendar contains the most up-to-date information about deadlines. Check back for changes.

Submit everything in Gradescope. If you miss class, Labs can be found in Gradescope and should be submitted individually. Problem Sets can be found in Gradescope as well.

Last updated: 8/2/2024

DateTopics/ActivitiesReadings and Deadlines
Th Aug 29Introduction to the Course, Review of ProofsTo-do: before the first day of class
Sun Sept 1Due: Lab from 8/29
Tu Sept 3Mathematical LiteracyReading: Sipser Chapter 0
Th Sept 5Finite AutomataReading: Sipser §1.1
Released today: Problem Set 1
Sun Sept 8Due: Labs from 9/3 and 9/5
Tu Sept 10NondeterminismReading: Sipser §1.2
Th Sept 12Regular ExpressionsReading: Sipser §1.3
Due: Problem Set 1
Released today: Problem Set 2
Sun Sept 15Due: Labs from 9/10 and 9/12
Tu Sept 17Regular ModelsReading: Decision Procedures
Th Sept 19IrregularityReading: Sipser §1.4
Due: Problem Set 2
Released today: Problem Set 3
Sun Sept 22Due: Labs from 9/17 and 9/19
Tu Sept 24Context-Free GrammarsReading: Sipser §2.1
Th Sept 26Turing MachinesReading: Sipser §3.1
Due: Problem Set 3
Released today: Problem Set 4
Sun Sept 29Due: Labs from 9/24 and 9/26
Tu Oct 1Variants of Turing MachinesReading: Sipser §3.2
Th Oct 3Time ComplexityReading: Sipser §7.1 and §7.2
Due: Problem Set 4
Sun October 6Due: Labs from 10/1 and 10/3
Tu Oct 8Exam 1
Th Oct 10NP-completenessReading: Sipser §7.3 through page 304
Released today: Problem Set 5
Sun Oct 13Due: Lab from 10/10
Tu Oct 15The Cook-Levine TheoremReading: Sipser pg 304-311
Th Oct 17More NP-completenessReading: Sipser §7.5
Due: Problem Set 5
Sun Oct 20Due: Labs from 10/15 and 10/17
10/21 - 10/25No Class: Fall Break
Tu Oct 29Savitch's TheoremReading: Sipser §8.1 and §8.2
Th Oct 31PSPACE-completenessReading: Sipser §8.3
Released today: Problem Set 6
Sun Nov 3Due: Labs from 10/29 and 10/31
Tu Nov 5L and NLReading: Sipser §8.4 - §8.6
Th Nov 7IntractabilityReading: Sipser §9.1 and §9.2

Due: Problem Set 6
Sun Nov 10Due: Labs from 11/5 and 11/7
Tu Nov 12Exam 2
Th Nov 14DecidabilityReading: Sipser §4.1
Released today: Problem Set 7
Sun Nov 17Due: Lab from 11/14
Tu Nov 19UndecidabilityReading: Sipser §4.2
Th Nov 21ReducibilityReading: Sipser §5.1 and §5.3

Due: Problem Set 7
Released today: Problem Set 7
Sun Nov 24Due: Labs from 11/19 and 11/21
Tu Nov 26A simple, undecidable problemReading: Sipser §5.2
Th Nov 28No Class, Thanksgiving
Sun Dec 1Due: Lab from 11/26
T Dec 3Rice's TheoremReading: Rice’s Theorem
Th Dec 5The Recursion TheoremReading: Sipser §6.1 and §6.2

Due: Problem Set 7
Released today: Problem Set 8
Sun Dec 8Due: Labs from 12/3 and 12/5
T Dec 10Approximation AlgorithmsReading: Sipser §10.1 and §10.2
Th Dec 12Wrap-up, course evaluationsNo reading today!
Due: Problem Set 8
Sun Dec 15Due: Labs from 12/10 and 12/12
12/17 - 12/20Exam 3
css.php
The views and opinions expressed on individual web pages are strictly those of their authors and are not official statements of Grinnell College. Copyright Statement.