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: January 2, 2025

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

Due: Problem Set 6
Th April 10Exam 2
Sun April 13Due: Lab from 4/8
Tu April 15DecidabilityReading: Sipser §4.1
Th April 17UndecidabilityReading: Sipser §4.2
Sun April 20Due: Labs from 4/15 and 4/17
Tu April 22ReducibilityReading: Sipser §5.1 and §5.3
Released today: Problem Set 7
Th April 24A simple, undecidable problemReading: Sipser §5.2
Sun April 27Due: Labs from 4/24 and 4/27
Tu April 29Rice's TheoremReading: Rice’s Theorem
Due: Problem Set 7
Released today: Problem Set 8
Th May 1The Recursion TheoremReading: Sipser §6.1 and §6.2
Sun May 4Due: Labs from 4/29 and 5/1
Tu May 6Approximation AlgorithmsReading: Sipser §10.1 and §10.2
Due: Problem Set 8
Th May 8Wrap-up, course evaluationsNo reading today!
Sun May 11Due: Labs from 5/6 and 5/8
Friday May 16Exam 3, 9am - 10:20am
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.