Course Schedule

Weekday Regular Schedule

Group Type Hours Location
08 Lecture Wed 10-13 Dan-David 001
09 Recitation Thu 12-13 Shenkar 222
XX Recitation Thu 13-14 Orenstain 110
10 Recitation Thu 14-15 Orenstain 110
11 Lecture Mon 13-16 Dah 005
12 Recitation Wed 15-16 Shenkar 104
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

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

Lecture 1;

2 March 6 & 11 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 13 & 18 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 April 3 & 8 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 10 & 22 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. Lecture 5;
April 24 No Class!
6 April 17 & 29 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 1 & 6 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 8 & 13 Mapping reductions. More undecidable languages. Rice theorem. Sipser, Sections 5.1, 5.3. Lecture 8.
9 May 20 & 22 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 27 & 29 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 3 & 5 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 10 & 12 Additional poly time reductions. Sipser, sections 7.5. Lecture 12
and
3SAT to Hamiltonian-Path—]
13 June 17 & 19 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 2012 course page

Spring 2011 course page

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