| CS 360 Introduction to the Theory of Computing | Winter 2010 |
Topics: models of computation --- finite automata, regular languages, pushdown automata, context free languages, turing machines. Decidable problems, undecidable problems, and other mathematical notions and techniques needed in the study of computation.
Below is the basic schedule of lectures along with associated readings from the text, I'll update this as we proceed.
| Date | Topic | Reading |
| Jan 5 | Course overview | 1-1.4 |
| Jan 7 | Alphabets, strings, languages; DFAs; Regular Languages | 1.5, 2 |
| Jan 12 | NFAs; Equivalence of NFAs and DFA's | 2 |
| Jan 14 | Closure Properties of Regular Languages | 4.1, 4.2 |
| Jan 19 | Regular Expressions | 3 |
| Jan 21 | Equivalence with DFAs; Testing Emptiness of Regular Languages; | 3, 4 |
| Jan 26 | Properties of Regular Languages | 4 |
| Jan 28 | Pumping Lemma for Regular Languages; Non-regular languages | 4 |
| Feb 2 | Context Free Grammars | 5.1, 5.2 |
| Feb 4 | Test 1 | |
| Feb 9 | Examples of CFG | |
| Feb 11 | Chomsky Normal Form | 7.1 |
| Feb 23 | Pushdown Automata | 6.2, 6.3 |
| Feb 25 | Equivalence of PDAs and CFGs | 6.3 |
| Mar 2 | Test 2 | |
| Mar 4 | Pumping Lemma for Context Free Languages | 7.2 |
| Mar 9 | Closure Properties of Context Free Languages | 7.3 |
| Mar 11 | Turing Machines Introduction | 8 |
| Mar 16 | Turing Machines, Syntax, Semantics, Examples | |
| Mar 18 | Test 3 | |
| Mar 23 | Turing Machine Variants | |
| Mar 25 | Nondeterministic Turing Machines, abstract descriptions of Turing Machines | |
| Mar 30 | Undecidable languages, non-Turing recognizable languages, Universal Turing Machines | 9 |
| Apr 1 | Halting Problem for deterministic Turing Machines | |