Course Schedule

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:

  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
1 March 9 & 11 Administratrivia. Introduction. Finite automata. Regular languages. Closure properties: Union. Chapter 1, Section 1.1.

Intro

Lecture 1

Recitation 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

Recitation 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

Recitation 3

4 April 13 & March 30 Context free languages. Context free grammars. Sipser, Section 2.1 Lecture 4

Recitation 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

Recitation 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

Recitation 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

Recitation 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

Recitation 8

9 May 18 & 20 Mapping reductions. More undecidable languages. Rice theorem. Sipser, Sections 5.1, 5.3. Lecture 9

Recitation 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

Recitation 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

Recitation 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

Recitation 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

Recitation 13

Previous Year's Course and Videos

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