CS 373: Introduction to Theory of Computation
Spring 2013
Below is a tentative schedule of the sequence of topics that will covered in this class; schedule may change upon the discretion of the instructors. Page numbers, section numbers, etc. in the table below refer to the corresponding items in the textbook "Introduction to the Theory of Computation" by Michael Sipser; below "S2" refers to the second edition, while "S3" refers to the third edition.
| Lecture Number | Date | Material covered | Readings | Quiz and Homework |
|---|---|---|---|---|
| 1 | 1/15 | Administrivia, overview, and basic definitions | S2,S3: chap 0 | No Quiz |
| disc 1 | 1/16 | Discrete mathematics review | S2,S3: chap 0 | |
| 2 | 1/17 | Deterministic Finite Automata | S2,S3: pp. 31--43 | Quiz on basic math; HW1 assigned |
| 3 | 1/22 | Proofs about DFAs | Quiz on Lec. 2 | |
| disc 2 | 1/23 | Deterministic Finite Automata Examples | S2,S3: pp. 31--43 | |
| 4 | 1/24 | Nondeterministic Finite Automata (NFA) | S2,S3: pp. 47--54 | Quiz on Lec. 3; HW1 due; HW2 assigned |
| 5 | 1/29 | Equivalence of DFA and NFA | S2,S3: pp. 54--58 | Quiz on Lec. 4 |
| disc 3 | 1/30 | Nondeterministic Finite Auotmata | S2,S3: pp. 47--58 | |
| 6 | 1/31 | Regular Expressions | S2,S3: pp. 63--66 | Quiz on Lec. 5; HW2 due; HW3 assigned |
| 7 | 2/5 | Regular expressions and finite automata | S2,S3: pp. 66--76 | Quiz on Lec. 6 |
| disc 4 | 2/6 | Regular Expressions | S2,S3: pp. 63--76 | |
| 8 | 2/7 | Closure Properties | S2,S3: pp. 45--47, 58--62 | Quiz on Lec. 7; HW3 due; HW4 assigned |
| 9 | 2/12 | Non-regular languages | S2,S3: pp. 77 | Quiz on Lec. 8 |
| disc 5 | 2/13 | Non-regular languages | S2,S3: pp. 45--47, 58--62, 77 | |
| 10 | 2/14 | Pumping Lemma | S2,S3: pp. 77--82 | Quiz on Lec. 9; HW4 due |
| 11 | 2/19 | Myhill-Nerode Theorem | S2,S3: problems 1.50,1.51 pp. 90--91 | Quiz on Lec. 10 |
| disc 6 | 2/20 | Pumping Lemma | S2,S3: pp. 77--82 | |
| -- | 2/21 | No lecture; Midterm 1 between 7 and 8:30pm | S2,S3: chapter 1 | HW5 assigned |
| 12 | 2/26 | Context-free languages and Ambiguity | S2: pp. 99--106; S3: pp. 101--108 | Quiz on Lec. 11 |
| disc 7 | 2/27 | Context-free languages and Ambiguity | S2: pp. 99--106; S3: pp. 101--108 | |
| 13 | 2/28 | Pushdown Automata | S2: pp. 109--114; S3: pp. 111--116 | Quiz on Lec. 12; HW5 due; HW6 assigned |
| 14 | 3/5 | Grammar Simplification | S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 12 (ambiguity) and Lec. 13 |
| disc 8 | 3/6 | Pushdown Automata | S2: pp. 109--114; S3: pp. 111--116 | |
| 15 | 3/7 | Normal Forms and Closure Properties | S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 14; HW6 due; HW7 assigned |
| 16 | 3/12 | Closure Properties | Quiz on Lec. 15 | |
| disc 9 | 3/13 | Closure Properties | ||
| 17 | 3/14 | Pumping Lemma and non-CFLs | S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 16; HW7 due; practice homework |
| 18 | 3/26 | Chomsky Hierarchy | Quiz on Lec. 17 | |
| disc 10 | 3/27 | Non CFLs | S2: pp 106--109; S3: pp. 108--111 | |
| -- | 3/28 | No lecture; Midterm 2 between 7 and 8:30pm | S2,S3: chapter 2 | |
| 19 | 4/2 | Turing Machines | S2: pp. 137--147; S3: pp. 165--175 | Quiz on Lec. 18 |
| disc 11 | 4/3 | Chomsky Hierarchy and Turing Machines | ||
| 20 | 4/4 | Variants of Turing Machines and the Church-Turing thesis | S2: pp. 148--154; S3: 176--182 | Quiz on Lec. 19; HW8 assigned |
| 21 | 4/9 | Decidable and Recognizable Languages | S2: pp. 165--173; S3: pp. 193--201 | Quiz on Lec. 20 |
| disc 12 | 4/10 | Turing Machine variants and decidability | S2,S3: chap. 3 | |
| 22 | 4/11 | Undecidable and Unrecognizable languages | S2: pp. 173--182; S3: pp. 201--210 | Quiz on Lec. 21; HW8 due; HW9 assigned |
| 23 | 4/16 | Reductions | S2,S3: chapter 5 | Quiz on Lec. 22 |
| disc 13 | 4/17 | Reductions | S2,S3: chap. 4 and 5 | |
| 24 | 4/18 | More Reductions (same notes as Lec. 23) | S2,S3: chapter 5 | Quiz on Lec. 23; HW9 due; HW10 assigned |
| 25 | 4/23 | Rice's Theorem | S2,S3: problem 5.28 | Quiz on Lec. 23-24 |
| disc 14 | 4/24 | Rice's Theorem | S2,S3: chap. 5 | |
| 26 | 4/25 | Closure Properties | Quiz on Lec. 25; HW10 due | |
| 27 | 4/30 | Closure properties continued | TBA | Quiz on Lec. 26 |
| disc 15 | 5/1 | P and NP | S2,S3: chap. 7 |
Acknowledgements: The lecture notes have been strongly influenced both in form and content by discussions with and slides, talks, lectures and notes of the following people: Gul Agha, Margaret Fleck, Sariel Har Peled, P. Madhusudan, Steven Pinker, Leonard Pitt, Manoj Prabhakaran, and Steven Rudich