Course Schedule
Table of Contents
Weekday Regular Schedule
| Group | Type | Hours | Location |
|---|---|---|---|
| 05 | Lecture | Wed 10-13 | Wolfson Tao 001 |
| 06 | Recitation | Thu 12-13 | Schreiber 06 |
| 07 | Recitation | Thu 12-13 | Schreiber 08 |
| 08 | Recitation | Thu 14-15 | Dan-David 03 |
| 09 | Lecture | Mon 13-16 | Dan-David 03 |
| 10 | Recitation | Wed 15-16 | Schreiber 06 |
| 11 | Recitation | Wed 14-15 | Schreiber 06 |
| 12 | Recitation | Thu 13-14 | Dan-David 110 |
Course Plan
The course roughly consists of four parts:
- Lectures 1-3: Languages and automata theory: Regular languages.
- Lectures 4-6: Languages and automata theory: Context-free languages.
- Lectures 7-10: Computability theory.
- Lectures 11-13: Introduction to complexity theory.
Detailed Schedule
| Lecture | Date | Lecture topics | Textbook references | Lecture slides | Recitation notes |
| 1 | March 9 & 11 | Administratrivia. Introduction. Finite automata. Regular languages. Closure properties: Union. | Chapter 1, Section 1.1. | ||
| 2 | March 16 & 18 | Non-Deterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata via generalized NFAs. | Chapter 1, Sections 1.1-1.3] | Lecture 2 | |
| 3 | March 23 & 25 | Two approaches for proving a language is non-regular: (1) Myhill-Nerode theorem (2) the pumping lemma. Computational questions stemming from finite automata. | Sipser, Sections 1.4, 2.1-2.2. Hopcroft and Ullman, Section 3.4. | Lecture 3 | |
| 4 | April 13 & March 30 | Context free languages. Context free grammars. | Sipser, Section 2.1 | Lecture 4 | |
| 5 | April 20 & 15 | Algorithmic properties of CFLs. Chomsky normal form of a CFG. Pumping lemma for CFGs. Push Down Automata. | Sipser, Sections 2.1, 2.2, 2.3. | Lecture 5 | |
| 6 | April 27 & 29 | More on CFLs and PDAs: Non-determinism adds power to PDAs. Non determinism vs. ambiguity in CFLs. Closure properties of CFLs. Algorithmic properties about CFLs. The equivalence theorem: CFLs vs. PDAs. | Sipser, Sections 2.1, 2.2, 2.3. | Lecture 6 | |
| 7 | May 4 & 6 | Turing Machines, Formal definition, Multi-tape TMs, RAMs, Church-Turing thesis | Sipser, Sections 3.1,3.2,3.3 | Lecture 7 | |
| 8 | May 11 & 13 | Non-Deterministic TMs. Encoding of TMs. A universal TM. The Halting /Acceptance problems are undecidable. | Sipser, Sections 3.2, 3.3, 4.1, 4.2. | Lecture 8 | |
| 9 | May 18 & 20 | Mapping reductions. More undecidable languages. Rice theorem. | Sipser, Sections 5.1, 5.3. | Lecture 9 | |
| 10 | May 25 & 27 | Mapping reductions. Rice theorem. Reductions using controlled executions. RE Completeness. Reductions using computation histories. Linear Bounded Automata. |
Sipser, Sections 5.1, 5.3. | Lecture 10 | |
| 11 | June 1 & 3 | Deterministic and non-deterministic time classes. A time lower bound. The classes P and NP and examples of languages in each. The class coNP. Verifiability. | Sipser, Sections 7.1. - 7.3 | Lecture 11 | |
| 12 | June 8 & 10 | The classes P and NP and examples of languages in each. Verifiability. The class coNP. NP-completeness. Polynomial time reductions. | Sipser, chapter 7.4 and 7.5 | Lecture 12 | |
| 13 | June 15 & 17 | NP-completeness of SAT, 3SAT, Hamiltonian Path, and Subset-Sum. | Sipser, chapter 7.4 and 7.5. | Lecture 13 and 3SAT to Hamiltonian-Path |
Previous Year's Course and Videos
Spring 2013 course page - 2013's recitations (by Oren Salzman) were filmed and are available here.
Spring 2009 course page - This also contains links to videos of almost all classes (by Benny Chor) and recitations (by Rani Hod).
Filmed lectures and recitations are not going to be identical to this year, but they will give you a pretty good idea, in case you had to or decided to miss some classes or recitations (due to, say, urgent business on the beach).
