CS 373: Introduction to Theory of Computation
Fall 2012
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 | 8/28 | Administrivia, overview, and brief history of computing | S2,S3: chap 0 | No Quiz |
| disc 1 | 8/28--8/29 | Discrete mathematics review | S2,S3: chap 0 | |
| 2 | 8/30 | Deterministic Finite Automata | S2,S3: pp. 31--43 | No Quiz; HW1 assigned |
| 3 | 9/4 | Proofs about DFAs | Quiz on Lec. 2 | |
| disc 2 | 9/4--9/5 | Deterministic Finite Automata Examples | S2,S3: pp. 31--43 | |
| 4 | 9/6 | Nondeterministic Finite Automata (NFA) | S2,S3: pp. 47--54 | Quiz on Lec. 3; HW1 due; HW2 assigned |
| 5 | 9/11 | Equivalence of DFA and NFA | S2,S3: pp. 54--58 | Quiz on Lec. 4 |
| disc 3 | 9/11-9/12 | Nondeterministic Finite Auotmata | S2,S3: pp. 47--58 | |
| 6 | 9/13 | Regular Expressions | S2,S3: pp. 63--66 | Quiz on Lec. 5; HW2 due; HW3 assigned |
| 7 | 9/18 | Regular expressions and finite automata | S2,S3: pp. 66--76 | Quiz on Lec. 6 |
| disc 4 | 9/18-9/19 | Regular Expressions | S2,S3: pp. 63--76 | |
| 8 | 9/20 | Closure Properties | S2,S3: pp. 45--47, 58--62 | Quiz on Lec. 7; HW3 due; HW4 assigned |
| 9 | 9/25 | Non-regular languages | S2,S3: pp. 77 | Quiz on Lec. 8 |
| disc 5 | 9/25-9/26 | Non-regular languages | S2,S3: pp. 45--47, 58--62, 77 | |
| 10 | 9/27 | Pumping Lemma | S2,S3: pp. 77--82 | Quiz on Lec. 9 |
| 11 | 10/2 | Myhill-Nerode Theorem | S2,S3: problems 1.50,1.51 pp. 90--91 | Quiz on Lec. 10 |
| disc 6 | 10/2-10/3 | Pumping Lemma | S2,S3: pp. 77--82 | |
| -- | 10/4 | No lecture; Midterm 1 between 7 and 9pm | S2,S3: chapter 1 | |
| 12 | 10/9 | Context-free languages and Ambiguity | S2: pp. 99--106; S3: pp. 101--108 | Quiz on Lec. 11 |
| disc 7 | 10/9-10/10 | Context-free languages and Ambiguity | S2: pp. 99--106; S3: pp. 101--108 | |
| 13 | 10/11 | Pushdown Automata | S2: pp. 109--114; S3: pp. 111--116 | Quiz on Lec. 12; HW5 assigned |
| 14 | 10/16 | Grammar Simplification | S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 12 (ambiguity) and Lec. 13 |
| disc 8 | 10/16-10/17 | Pushdown Automata | S2: pp. 109--114; S3: pp. 111--116 | |
| 15 | 10/18 | Normal Forms and Closure Properties | S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 14; HW5 due; HW6 assigned |
| 16 | 10/23 | Closure Properties: Homomorphisms | Quiz on Lec. 15 | |
| disc 9 | 10/23-10/24 | Closure Properties | ||
| 17 | 10/25 | Pumping Lemma and non-CFLs | S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 16; HW6 due; HW7 assigned |
| 18 | 10/30 | Chomsky Hierarchy | Quiz on Lec. 17 | |
| disc 10 | 10/30-10/31 | Non CFLs | S2: pp 106--109; S3: pp. 108--111 | |
| 19 | 11/1 | Turing Machines | S2: pp. 137--147; S3: pp. 165--175 | Quiz on Lec. 18; HW7 due |
| 20 | 11/6 | Variants of Turing Machines and the Church-Turing thesis | S2: pp. 148--154; S3: 176--182 | Quiz on Lec. 19 |
| disc 11 | 11/6-11/7 | Chomsky Hierarchy | ||
| -- | 11/8 | No lecture; Midterm 2 between 7 and 8:30pm | S2,S3: chapter 2 and Chomsky Hierarchy | HW8 assigned |
| 21 | 11/13 | Decidable and Recognizable Languages | S2: pp. 165--173; S3: pp. 193--201 | Quiz on Lec. 20 |
| disc 12 | 11/13-11/14 | Turing Machines | S2,S3: chap. 3 | |
| 22 | 11/15 | Undecidable and Unrecognizable languages | S2: pp. 173--182; S3: pp. 201--210 | Quiz on Lec. 21; HW8 due |
| 23 | 11/27 | Reductions | S2,S3: chapter 5 | Quiz on Lec. 22; HW9 assigned |
| disc 13 | 11/27-11/28 | Reductions | S2,S3: chap. 4 and 5 | |
| 24 | 11/29 | Rice's Theorem and Closure Properties | S2,S3: problem 5.28 | Quiz on Lec. 23 |
| 25 | 12/4 | Polynomial Time | S2: pp. 247--263; S3: pp. 275--291 | Quiz on Lec. 24; HW9 due; HW10 assigned |
| disc 14 | 12/4-12/5 | Rice's Theorem and Closure Properties | S2,S3: chap. 5 | |
| 26 | 12/6 | Nondeterministic Polynomial Time | S2: pp. 264--270; S3: pp. 292--298 | Quiz on Lec. 25 |
| 27 | 12/11 | NP-completeness | S2: pp. 271--294; S3: pp. 299--322 | Quiz on Lec. 26; HW10 due |
| disc 15 | 12/11-12/12 | 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