## CS 373: Introduction to Theory of Computation

### Lecture Schedule and Notes

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
--
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