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.
Video lectures can be found here.
Lecture Number | Date | Material covered | Readings | Quiz and Homework |
---|---|---|---|---|
1 | 8/27 | Administrivia, overview, and basic definitions | S2,S3: chap 0 | No Quiz |
disc 1 | 8/27-8/28 | Discrete mathematics review | S2,S3: chap 0 | |
2 | 8/29 | Deterministic Finite Automata
Video Links: Rich media, Vodcast, Podcast |
S2,S3: pp. 31--43 | Quiz on basic math; HW1 assigned |
3 | 9/3 | Proofs about DFAs
Video Links: Rich media, Vodcast, Podcast |
Quiz on Lec. 2 | |
disc 2 | 9/3-9/4 | Deterministic Finite Automata Examples | S2,S3: pp. 31--43 | |
4 | 9/5 | Nondeterministic Finite Automata (NFA)
Video Links: Rich media, Vodcast, Podcast |
S2,S3: pp. 47--54 | Quiz on Lec. 3; HW1 due; HW2 assigned |
5 | 9/10 | Equivalence of DFA and NFA
Video Links: Rich media, Vodcast, Podcast |
S2,S3: pp. 54--58 | Quiz on Lec. 4 |
disc 3 | 9/10-9/11 | Nondeterministic Finite Auotmata | S2,S3: pp. 47--58 | |
6 | 9/12 | Regular Expressions
Video Links: Rich media, Vodcast, Podcast |
S2,S3: pp. 63--66 | Quiz on Lec. 5; HW2 due; HW3 assigned |
7 | 9/17 | Regular expressions and finite automata
Video Links: Rich media, Vodcast, Podcast |
S2,S3: pp. 66--76 | Quiz on Lec. 6 |
disc 4 | 9/17-9/18 | Regular Expressions | S2,S3: pp. 63--76 | |
8 | 9/19 | Closure Properties
Video Links: Rich media, Vodcast, Podcast |
S2,S3: pp. 45--47, 58--62 | Quiz on Lec. 7; HW3 due; HW4 assigned |
9 | 9/24 | Closure properties (contd); same notes as lecture 8
Video Links: Rich media, Vodcast, Podcast |
S2,S3: pp. 77 | Quiz on Lec. 8 |
disc 5 | 9/24-9/25 | Closure properties | S2,S3: pp. 45--47, 58--62, 77 | |
10 | 9/26 | Non-regular languages and Pumping Lemma
Video Links: Rich media, Vodcast, Podcast |
S2,S3: pp. 45--47, 58--62, 77--82 | Quiz on Lec. 9; HW4 due |
11 | 10/1 | Myhill-Nerode Theorem
Video Links: Rich media, Vodcast, Podcast |
S2,S3: problems 1.50,1.51 pp. 90--91 | Quiz on Lec. 10 |
disc 6 | 10/1-10/2 | Pumping Lemma | S2,S3: pp. 77--82 | |
-- | 10/3 | No lecture; Midterm 1 between 7 and 8:30pm | S2,S3: chapter 1 | HW5 assigned |
12 | 10/8 | Context-free languages and Ambiguity
Video Links: Rich media, Vodcast, Podcast |
S2: pp. 99--106; S3: pp. 101--108 | Quiz on Lec. 11 |
disc 7 | 10/8-10/9 | Context-free languages and Ambiguity | S2: pp. 99--106; S3: pp. 101--108 | |
13 | 10/10 | Pushdown Automata
Video Links: Rich media, Vodcast, Podcast |
S2: pp. 109--114; S3: pp. 111--116 | Quiz on Lec. 12; HW5 due; HW6 assigned |
14 | 10/15 | Closure Properties
Video Links: Rich media, Vodcast, Podcast |
Quiz on Lec. 12 (ambiguity) and Lec. 13 | |
disc 8 | 10/15-10/16 | Pushdown Automata | S2: pp. 109--114; S3: pp. 111--116 | |
15 | 10/17 | Pumping Lemma and non-CFLs
Video Links: Rich media, Vodcast, Podcast |
S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 14; HW6 due; HW7 assigned |
16 | 10/22 | Grammar Simplification
Video Links: Rich media, Vodcast, Podcast |
S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 15 |
disc 9 | 10/22-10/23 | Closure Properties and non-CFL Languages | S2: pp 106--109; S3: pp. 108--111 | |
17 | 10/24 | Normal Forms
Video Links: Rich media, Vodcast, Podcast |
S2: pp 106--109; S3: pp. 108--111 | Quiz on Lec. 16; HW7 due |
18 | 10/29 | Chomsky Hierarchy
Video Links: Rich media, Vodcast, Podcast |
Quiz on Lec. 17 | |
disc 10 | 10/29-10/30 | Normal Forms of Grammars and Chomsky Hierarchy | S2: pp 106--109; S3: pp. 108--111 | |
-- | 10/31 | No lecture; Midterm 2 between 7 and 8:30pm | S2,S3: chapter 2 | |
19 | 11/5 | Turing Machines
Video Links: Rich media, Vodcast, Podcast |
S2: pp. 137--147; S3: pp. 165--175 | Quiz on Lec. 18 |
disc 11 | 11/5-11/6 | Chomsky Hierarchy and Turing Machines | ||
20 | 11/7 | Variants of Turing Machines and the Church-Turing thesis
Video Links: Rich media, Vodcast, Podcast |
S2: pp. 148--154; S3: 176--182 | Quiz on Lec. 19; HW8 assigned |
21 | 11/12 | Decidable and Recognizable Languages
Video Links: Rich media, Vodcast, Podcast |
S2: pp. 165--173; S3: pp. 193--201 | Quiz on Lec. 20 |
disc 12 | 11/12-11/13 | Turing Machine variants and decidability | S2,S3: chap. 3 | |
22 | 11/14 | Undecidable and Unrecognizable languages
Video Links: Rich media, Vodcast, Podcast |
S2: pp. 173--182; S3: pp. 201--210 | Quiz on Lec. 21; HW8 due; HW9 assigned |
23 | 11/19 | Reductions
Video Links: Rich media, Vodcast, Podcast |
S2,S3: chapter 5 | Quiz on Lec. 22 |
disc 13 | 11/19-11/20 | Reductions | S2,S3: chap. 4 and 5 | |
24 | 11/21 | More Reductions (same notes as Lec. 23)
Video Links: Rich media, Vodcast, Podcast |
S2,S3: chapter 5 | Quiz on Lec. 23; HW9 due |
25 | 12/3 | Rice's Theorem
Video Links: Rich media, Vodcast, Podcast |
S2,S3: problem 5.28 | Quiz on Lec. 23-24; HW10 assigned |
disc 14 | 12/3-12/4 | Rice's Theorem | S2,S3: chap. 5 | |
26 | 12/5 | Closure Properties
Video Links: Rich media, Vodcast, Podcast |
Quiz on Lec. 25 | |
27 | 12/10 | Closure properties continued | TBA | Quiz on Lec. 26; HW10 due |
disc 15 | 12/10-12/11 | Review | S2,S3: chap. 3,4,5 |
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