Course Schedule

Weekday Regular Schedule

Group Type Hours Location
08 Lecture Wed 10-13 Wolfson 001
09 Recitation Thu 12-13 Orenstein 103
10 Recitation Thu 08-09 Orenstain 111
11 Lecture Mon 13-16 Dan-David 001
12 Recitation Wed 15-16 Kaplun 118
13 Recitation Wed 14-15 Kaplun 118

Course Plan

The course roughly consists of three parts:

  1. Lectures 1-5: languages and automata theory.
  2. Lectures 6-10: computability theory.
  3. Lectures 11-13: complexity theory.

Detailed Schedule

Week Date Lecture topics Textbook references Lecture slides
1 March 5 & 7 Administratrivia. Some mathematical preliminaries. Finite automata. Regular languages. Closure properties: Union. Chapter 0. Chapter 1, Section 1.1. Intro;

Lecture 1;

2 March 12 & 14 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 19 & 21 Two approaches for proving a language is non-regular: (1) Myhill-Nerode theorem (2) the pumping lemma. Computational questions stemming from finite automata. Context free grammars. Sipser, Sections 1.4, 2.1-2.2. Hopcroft and Ullman, Section 3.4. Lecture 3.
4 March 26 & 28 Pumping lemma for context free grammars. Examples for non context free languages. Push down automata (non-deterministic and deterministic). The equivalence theorem: CFL vs. PDAs. Examples of languages accepted by PDAs. Sipser, Sections 2.1, 2.2, 2.3. Lecture 4.
April 2 canceled
5 April 16 & 18 Non-determinism adds power to PDAs. Non determinism vs. ambiguity in CFLs. Closure properties of CFLs. Algorithmic properties about CFLs. Chomsky normal form of a CFG. The equivalence theorem: CFLs vs. PDAs. Sipser, Sections 2.1, 2.2, 2.3. Lectures 5.
April 23 review for mid-tem
6 April 30 & May 2 Turing Machines. Alternative Models of Computers: Multi tape TMs, RAMs,
Non Deterministic TMs. The language classes R, RE and coRE.
Sipser, Sections 3.1, 3.2. Lecture 6.
7 May 7 & 9 Church-Turing thesis. Hilbert's 10th problem. Encoding of Turing Machines. A universal TM. The halting / acceptance problems are undecidable. Sipser, Sections 3.2, 3.3, 4.1, 4.2. Lecture 7.
8 May 14 & 16 Mapping reductions. More undecidable languages. Rice theorem. Sipser, Sections 5.1, 5.3. Lecture 8.
9 May 21 & 23 Mapping reductions. Rice theorem. Reductions using controlled executions. RE Completeness. Reductions using computation histories.
Linear Bounded Automata. Unrestricted grammars.
Sipser, Sections 5.1, 5.3. Lecture 9.
10 May 28 &30 Deterministic and non-deterministic time classes. The classes P and NP and examples of languages in each. The class coNP. Verifiability. Sipser, Sections 7.1. - 7.3 Lecture 10.
11 June 4 & 6 Deterministic and non-deterministic time classes. The classes P and NP and examples of languages in each. The class coNP. Verifiability. Sipser, chapter 7.4 and 7.5 Lecture 11.
12 June 11 & 13 Additional poly time reductions. Sipser, sections 7.5. Lecture 12
and
3SAT to Hamiltonian-Path
13 June 18 & 20 Optimization, search, and decision problems. Approximate solutions to optimization problems. Sipser, chapters 9.1 and 10.1-10.2. Lecture 13
14
15

Previous Year's Course and Videos

Spring 2011 course page: Very similar lectures and recitations.

Spring 2009 course page: In addition to lecture notes, this contains links to videos of almost all classes (by Benny Chor) and recitations (by Rani Hod).
The 2009 lectures 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