Schedule
Below is the tentative course schedule for the term. The “tentative” is key since the schedule will almost certainly change throughout the term.
| Week 1 | |||||
|---|---|---|---|---|---|
| Tue: 01/28 |
Introduction to Theory of Computation
Slides |
||||
| Thu: 01/30 |
Review of Discrete Mathematics
Slides |
Reading: Sipser 0.1–0.2 |
|||
| Week 2 | |||||
| Tue: 02/04 |
Writing Proofs
Slides |
Reading: Sipser 0.3–0.4 |
Due: Assignment 1 |
||
| Thu: 02/06 |
Deterministic Finite Automata
Slides |
Reading: Sipser 1.1 |
|||
| Week 3 | |||||
| Tue: 02/11 |
Nondeterministic Finite Automata
Slides |
Reading: Sipser 1.2 |
Due: Assignment 2 |
||
| Thu: 02/13 |
Regular Expressions
Slides |
Reading: Sipser 1.3 |
|||
| Week 4 | |||||
| Tue: 02/18 |
Properties of Regular Languages
Slides |
Due: Assignment 3 |
|||
| Thu: 02/20 |
Nonregular Languages
Slides |
Reading: Sipser 1.4 |
|||
| Week 5 | |||||
| Tue: 02/25 |
Pause for Breath
Slides |
Due: Assignment 4 |
|||
| Thu: 02/27 |
Exam 1
|
||||
| Week 6 | |||||
| Tue: 03/03 |
Turing Machines
Slides |
Reading: Sipser 3.1 |
|||
| Thu: 03/05 |
Turing Machine Variants
Slides |
Reading: Sipser 3.2 |
|||
| Week 7 | |||||
| Tue: 03/10 |
Algorithms
Slides |
Reading: Sipser 3.3 |
|||
| Thu: 03/12 |
Special Topic
Slides |
Due: Assignment 5 |
|||
| SPRING BREAK | |||||
| Week 8 | |||||
| Tue: 03/24 |
Decidability
Slides |
Reading: Sipser 4.1 |
|||
| Thu: 03/26 |
The Halting Problem
Slides |
Reading: Sipser 4.2 |
|||
| Week 9 | |||||
| Tue: 03/31 |
Undecidability
Slides |
Reading: Sipser 5.1 |
|||
| Thu: 04/02 |
Mapping Reducibility
Slides |
Reading: Sipser 5.3 |
Due: Assignment 6 |
||
| Week 10 | |||||
| Tue: 04/07 |
Pause for Breath
Slides |
Due: Assignment 7 |
|||
| Thu: 04/09 |
Exam 2
|
||||
| Week 11 | |||||
| Tue: 04/14 |
Introduction to Complexity Theory
|
||||
| Thu: 04/16 |
Measuring Complexity
Slides |
Reading: Sipser 7.1 |
|||
| Week 12 | |||||
| Tue: 04/21 |
The Class P
Slides |
Reading: Sipser 7.2 |
|||
| Thu: 04/23 |
The Class NP
Slides |
Reading: Sipser 7.3 |
|||
| Week 13 | |||||
| Tue: 04/28 |
NP Completeness
Slides |
Reading: Sipser 7.4 |
Due: Assignment 8 |
||
| Thu: 04/30 |
NP Completeness, Continued
Slides |
Reading: Sipser 7.5 |
Due: Assignment 9 (Questionnaire) |
||
| Week 14 | |||||
| Tue: 05/05 |
NP Completeness, Continued
Slides |
||||
| Thu: 05/07 |
Review for Exam
Slides |
Due: Assignment 9 (Video) |
|||
| Final Evaluation Week | |||||
| TBD | Final Exam | ||||