CS 373: Introduction to Theory of Computation

Fall 2013

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.

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