Despite the change in number (CS 273 to CS 373), the topics covered will roughly be the same and in the same order as that in Spring 2008; see schedule along with lecture notes used in Spring 2008.
Lecture notes are intended only to show what topics were covered, so you can find and read the corresponding sections in the textbook. They are not intended to be a substitute for the textbook and handouts. Page numbers, section numbers and chapter numbers below refer to the corresponding elements in the class textbook. The lecture by lecture slide version of the material is linked up below, along with a printer friendly "notes" version.
Consolidated versions of the notes will be posted periodically.
Acknowledgements: The lecture notes have been strongly influenced both in form and content by discssions with and slides, talks, lectures and notes of the following people: Margret Fleck, Sariel Har Peled, P. Madhusudan, Steven Pinker, Leonard Pitt, and Steven Rudich.
| Lecture Number | Date | Material covered | Readings/Handouts/Hyperlinks |
|---|---|---|---|
| 1 | 8/26 | Administrivia, overview, and brief history of computing (notes) | Chapter 0 |
| disc 1 | 8/26--8/27 | Discrete mathematics review | Chapter 0. Also Discrete Mathematics by W.L.L.Chen, chapters 1, 2, and 3 |
| 2 | 8/28 | Deterministic Finite Automata (DFA) (notes) | Pages 31 to 43 |
| 3 | 9/2 | ||
| disc 2 | 9/2--9/3 | Deterministic Finite Automata Examples | Pages 31 to 43 |
| 4 | 9/4 | Nondeterministic Finite Automata (NFA) (notes) | Pages 47 to 54 |
| 5 | 9/9 | Equivalence of DFA and NFA (notes) | Pages 54 to 58 |
| disc 3 | 9/9--9/10 | Nondeterministic Finite Automata Examples | Pages 47 to 58 |
| 6 | 9/11 | Regular Expressions (notes) | Pages 63 to 69 |
| 7 | 9/16 | Converting DFAs to Regular Expressions (notes) | Pages 69 to 76 |
| disc 4 | 9/16--9/17 | Regular Expression Examples | Pages 63 to 76 |
| 8 | 9/18 | Nonregular languages and Pumping Lemma (notes) | Pages 77 to 82 |
| 9 | 9/23 | Closure Properties of Regular Languages (notes) | Pages 45 to 47 and 58 to 62 |
| disc 5 | 9/23--9/24 | Nonregularity Examples | Pages 45 to 47, 58 to 62, and 77 to 82 |
| 10 | 9/25 | Myhill-Nerode Theorem and Minimization (notes) | Problem 1.52, page 91 |
| 11 | 9/30 | ||
| disc 6 | 9/30--10/1 | Review for Midterm | Chapter 1 |
| -- | 10/2 | Midterm 1 in MH 103 between 7pm and 9pm | Chapter 1 |
| 12 | 10/7 | Context-free Grammars and Ambiguity (notes) | Pages 99 to 106 |
| disc 7 | 10/7--10/8 | DFA Minimization and CFG examples | Problem 1.52, and pages 99 to 106 |
| 13 | 10/9 | Pushdown Automata (notes) | Pages 109 to 114 |
| 14 | 10/14 | Equivalence of CFGs and PDAs (notes) | Pages 115 to 122 |
| disc 8 | 10/14--10/15 | PDA examples | Pages 109 to 122 |
| 15 | 10/16 | Normal Forms of Grammars (notes) | Pages 106 to 108 |
| 16 | 10/21 | ||
| disc 9 | 10/14--10/15 | Normal Forms of Grammars | Pages 106 to 108 |
| 17 | 10/23 | Non-Context-Freeness and Pumping Lemma (notes) | Pages 123 to 127 |
| 18 | 10/28 | Closure Properties of CFLs (notes) | -- |
| disc 10 | 10/28--10/29 | Pumping Lemma, Closure Properties for CFLs. Review for midterm | Chapter 2 |
| 19 | 10/30 | CYK Algorithm and Chomsky Hierarchy (notes) | -- |
| -- | 11/4 | Midterm 2 in MSEB 100 between 7pm and 9pm | Chapter 2 |
| 20 | 11/6 | Introduction to Turing Machines (notes) | Pages 137 to 147 |
| 21 | 11/11 | Variants of Turing Machines and the Church-Turing Thesis (notes) | Pages 148 to 154 |
| disc 11 | 11/11--11/12 | Examples of Turing Machines | Chapter 3 |
| 22 | 11/13 | Decidability and Recognizability (notes) | Pages 165 to 173 |
| 23 | 11/18 | Undecidability and Unrecognizability (notes) | Pages 173 to 182 |
| disc 12 | 11/18--11/19 | Decidability, Undecidability etc. | Chapter 4 |
| 24 | 11/20 | Reductions, Rice's Theorem and Closure Properties (notes) | Pages 206 to 210 and problem 5.28 |
| -- | 11/22 to 12/1 | Thanksgiving break | -- |
| 25 | 12/2 | Application: Formal Verification | -- |
| disc 13 | 12/2--12/3 | Reducibility Examples | Chapter 5 |
| 26 | 12/4 | Application: Natural Language Processing | At 1310 DCL between 5 and 6:15pm |
| 27 | 12/9 | Application: Cryptography | -- |
| disc 14 | 12/9--12/10 | Course Review | Chapters 1 through 5 |