If links do not work in the table below, it likely means that they aren’t set to be released in Gradescope yet. If you believe something should be already released, shoot me an email.

DateTopics/ActivitiesReadings and DeadlinesLab
T Jan 25Introduction to the Course, Review of ProofsTo-do before the first day of class 1/25
Th Jan 27Mathematical LiteracyReading: Sipser: Chapter 0
Released today: Problem Set 1		1/27
Sat Jan 29Due: Labs from 1/25 and 1/27
T Feb 1Finite AutomataReading: Sipser: Section 1.12/1
Th Feb 3NondeterminismSipser: Section 1.2
You can just skim the section on Equivalence of NFAs and DFAs. 		2/3
Sat Feb 5Labs from 2/1 and 2/3
T Feb 8Regular ExpressionsReading: Sipser Section 1.3
Due: Problem Set 1
Released today: Problem Set 2		2/8
Th Feb 10Regular ModelsReading: Decision Procedures and questions2/10
Sat Feb 12Labs from 2/8 and 2/10
T Feb 15IrregularityReading: Sipser: Section 1.4
Due: Problem Set 2		2/15
Th Feb 17Context-Free GrammarsReading: Sipser: Section 2.1
Released today: Problem Set 3
Due: Problem Set 2		2/17
Sat Feb 19Labs from 2/15 and 2/17
T Feb 22Turing MachinesReading: Sipser: 3.12/22
Th Feb 24Variants of Turing MachinesReading: Sipser 3.2
Quiz opens today in Gradescope		2/24
Sat Feb 26Labs from 2/22 and 2/24
T Mar 1No Class: Working Differently DayReading: Sipser 3.3
Due: Problem Set 3
Th Mar 3Time ComplexityReading: Sipser 7.1-7.2
Released today: Problem Set 4		3/3
Sat Mar 5Lab from 3/3
T Mar 8NP-completenessReading: Sipser 7.3 through page 3043/8
Th Mar 10The Cook-Levine TheoremReading: Sipser pg 304-3113/10
Sat Mar 12Labs from 3/8 and 3/10
T Mar 15More NP-completenessReading: Sipser 7.5
Due today: Problem Set 4		3/15
Th Mar 17Savitch's TheoremReading: Sipser 8.1-8.23/17
Sat Mar 19Labs from 3/15 and 3/17
3/22 - 3/31No Class: Spring BreakProblem Set 5 posted
T April 5PSPACE-completenessSipser 8.34/5
Th April 7Catch-up dayNo reading today!
Quiz opens today		4/7
Sat April 9Labs from 4/5 and 4/7
T April 12L and NLSipser 8.4-8.6
Problem Set 5 due
Problem Set 6 posted		4/12
Th April 14IntractabilitySipser 9.14/14
Sat April 16Labs from 4/12 and 4/14
T April 19DecidabilitySipser 4.1
Problem Set 6 due		4/19
Th April 21UndecidabilitySipser 4.2
Problem Set 6 released today		4/21
Sat April 23Labs from 4/19 and 4/21
T April 26ReducibilitySipser 5.1 and 5.3
After reading Sipser, review this overview on the proof strategies from the reading.
Problem Set 7 due		4/26
Th April 28A simple, undecidable problemSipser 5.24/28
Sat April 30Labs from 4/26 and 4/28
T May 3Rice's TheoremReading, and link to questions
Problem Set 6 due
Problem Set 7 released today		5/3
Th May 5The Recursion TheoremSipser 6.1
Quiz opens today
Sat May 7Labs from 5/3 and 5/5
T May 10Approximation AlgorithmsSipser 10.1
Problem Set 8 due
Problem Set 7 due
Th May 12Wrap-up, course evaluationsNo reading today!
Sat May 13Labs from 5/10 and 5/12
May 16Exam WeekQuiz Make-ups (optional)
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.