Course Schedule

Weekday Regular Schedule

Grou Type Hours Location
05 Lecture Wed 10-13 Dach 05
06 Recitation Thu 12-13 Schreiber 06
07 Recitation Thu 14-15 Schreiber 06
08 Recitation Thu 14-15 Orenstein 111
09 Lecture Mon 13-16 Dach 05
10 Recitation Wed 15-16 Melamed 06
11 Recitation Wed 14-15 Melamed 06
12 Recitation Thu 13-14 Melamed 06
13 Recitation Thu 12-13 Melamed 06

Course Plan

The course roughly consists of four parts:

  1. Lectures 1-3: Languages and automata theory: Regular languages.
  2. Lectures 4-6: Languages and automata theory: Context-free languages.
  3. Lectures 7-10: Computability theory.
  4. Lectures 11-13: Introduction to complexity theory.

Detailed Schedule

]
Lecture Date Lecture topics Textbook references Lecture slides Recitation notes Recitation dates
1 Group 5: March 13
Group 9: March 15
Administratrivia. Introduction. Finite automata. Regular languages. Regular operations. Chapter 1. Lecture 1 Recitation 1 Dean: March 16
Yuval: March 15
Dafna: March 16
2 Group 5: March 20
Group 9: March 22
Non-Deterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata. Chapter 1, Sections 1.1-1.3 Lecture 2 Recitation 2 Dean: March 23
Yuval: March 22
Dafna: March 23
3 Group 5: March 27
Group 9: March 29
Three approaches for proving a language is non-regular: (1) Myhill-Nerode theorem (2) the pumping lemma (3) closure properties. Computational questions stemming from finite automata. Sipser, Sections 1.4, 2.1-2.2. Hopcroft and Ullman, Section 3.4.


Lecture 3

Alice&Bob

Recitation 3 Dean: March 30
Yuval: March 29
Dafna: March 30
4 Group 5: April 3
Group 9: April 19
Context free languages. Context free grammars.
Algorithmic properties of CFLs. Chomsky normal form of a CFG.
Sipser, Section 2.1,2.2, 2.3. Lecture 4 Recitation 4 Dean: April 20
Yuval: April 19
Dafna: April 20
5 Group 5: April 24
Group 9: April 26
Push Down Automata. The equivalence theorem: CFLs vs. PDAs. Sipser, Sections 2.1, 2.2, 2.3. Lecture 5 Recitation 5 Dean: April 27
Yuval: April 26
Dafna: April 27
6 Group 5: May 8
Group 9: May 3
More on CFLs and PDAs. Pumping lemma for CFGs. Closure properties of CFLs. Algorithmic properties about CFLs. Sipser, Sections 2.1, 2.2, 2.3. Lecture 6 Recitation 6 Dean: May 4
Yuval: May 10
Dafna: May 4
7 Group 5: May 15
Group 9: May 10
Turing Machines, Formal definition, Multi-tape TMs, RAMs, Church-Turing thesis Sipser, Sections 3.1,3.2,3.3 Lecture 7 Recitation 7 Dean: May 18
Yuval: May 17
Dafna: May 11
8 Group 5: May 22
Group 9: May 17
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 Recitation 8 Dean: June 1
Yuval: May 24
Dafna: May 18
9 Group 5: May 29
Group 9: May 24
Mapping reductions. More undecidable languages. Rice theorem. Sipser, Sections 5.1, 5.3. Lecture 9 Recitation 9 Dean: June 2
Yuval: June 2
Dafna: June 1
10 Group 5: June 5
Group 9: June 7
Kolmogorov Complexity Reductions using controlled executions. Reductions using computation histories. RE Completeness. Sipser, Sections 6.4, 5.1, 5.3. Lecture 10 Recitation 10 Dean: June 8
Yuval: June 7
Dafna: June 8
11 Group 5: June 12
Group 9: June 14
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 Recitation 11 Dean: June 15
Yuval: June 14
Dafna: June 15
12 Group 5: June 19
Group 9: June 21
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

Recitation 12

Dean: June 22
Yuval: June 21
Dafna: June 22
13 Group 5: June 26
Group 9: June 28
Dean: June 29
Yuval: June 28
Dafna: June 29

Previous Year's Course and Videos

Fall 2017 course page

Spring 2016 course page

Spring 2015 course page

Spring 2014 course page

Spring 2013 course page - 2013's recitations (by Oren Salzman) were filmed and are available here.

Spring 2012 course page

Spring 2011 course page

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

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License