Course Schedule
Table of Contents
Weekday Regular Schedule
Group  Type  Hours  Location 

08  Lecture  Wed 1013  DanDavid 001 
09  Recitation  Thu 1213  Shenkar 222 
10  Recitation  Thu 1415  Melamed 007 
11  Lecture  Mon 1316  DanDavid 001 
12  Recitation  Wed 1516  Shenkar 222 
13  Recitation  Wed 1415  Shenkar 222 
Note: The course is taught concurrently in two groups. While there will be some differences in presentation style and details, the material to be covered is the same. Homework assignments, midterm, and final exams will be identical for both groups.
Course Plan
The course roughly consists of three parts:
 Lectures 15: languages and automata theory.
 Lectures 610: computability theory.
 Lectures 1113: complexity theory.
Group 08 TimeTable (Prof. Yishay Mansour, Mr. Mariano Schain)
Week  Date  Lecture topics  Recitation topics and slides  Textbook references  Lecture slides 
1  Feb 23  Administratrivia. Some mathematical preliminaries. Finite automata. Regular languages. Closure properties: Union.  Regular Languages. DFAs. Closure properties: Intersection, Complement S 1; 
Chapter 0. Chapter 1, Section 1.1.  M 1 intro; M 1 DFA; 
2  Mar 2  NonDeterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata via generalized NFAs.  NFAs. Regular expressions. S 2; 
Chapter 1, Sections 1.11.3.  M 2; 
3  Mar 9  Two approaches for proving a language is nonregular: (1) MyhillNerode theorem (2) the pumping lemma. Computational questions stemming from finite automata. Context free grammars.  The pumping lemma for regular languages, Homomorphism. S 3; 
Sipser, Sections 1.4, 2.12.2. Hopcroft and Ullman, Section 3.4.  New Lecture 3. 
4  Mar 16  Pumping lemma for context free grammars. Examples for non context free languages. Push down automata (nondeterministic and deterministic). The equivalence theorem: CFL vs. PDAs. Examples of languages accepted by PDAs.  Writing contextfree grammars. Pumping lemma for CFLs S 4; 
Sipser, Sections 2.1, 2.2, 2.3.  New Lectures 4 and 5. 
5  Mar 23  Nondeterminism 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.  Closure properties for CFLs. PDAs S 5; 
Sipser, Sections 2.1, 2.2, 2.3.  New Lectures 5. 
6  Mar 30  Turing Machines. Alternative Models of Computers: Multi tape TMs, RAMs, Non Deterministic TMs. The language classes R, RE and coRE. 
Review, MyhillNerode, Turing Machine S 6; 
Sipser, Sections 3.1, 3.2.  New Lecture 6. 
7  April 6  ChurchTuring thesis. Hilbert's 10th problem. Encoding of Turing Machines. A universal TM. The halting / acceptance problems are undecidable.  TM construction (explicit).  Sipser, Sections 3.2, 3.3, 4.1, 4.2.  New Lecture 7. 
8  April 13  Mapping reductions. More undecidable languages. Rice theorem.  Pesah  Sipser, Sections 5.1, 5.3.  New Lecture 8. 
9  April 27  Mapping reductions. Rice theorem. Reductions using controlled executions. RE Completeness. Reductions using computation histories.  Decidability  Sipser, Sections 5.1, 5.3.  New Lecture 9. 
10  May 4  Linear Bounded Automata. Unrestricted grammars. Deterministic time classes. 
More reductions. Rice Theorem.  Sipser, Sections 5.3, 7.1.  New Lecture 10. 
11  May 11  Deterministic and nondeterministic time classes. The classes P and NP and examples of languages in each. The class coNP. Verifiability.  Mapping reductions  Sipser, chapter 7.2 and 7.3  NewLecture 11. 
12  May 18  The classes NP (reminder). Poly time Reductions. NP completeness.  Problems in NP (VC, IS). Polytime reductions.  Sipser, sections 7.3 and 7.4.  New Lecture 12. 
13  May 25  Additional poly time reductions.  Student Day  Sipser, chapter 7.5  New Lecture 13 hamreduction. 
14  June 1  Optimization, search, and decision problems. Approximate solutions to optimization problems.  More poly time reductions  Sipser, chapter 10.  New Lecture 14 
15  June 8  Shavout 
Group 11 TimeTable (Prof. Nachum Dershowitz, Mr. Ori Lahav)
Week  Date  Lecture topics  Textbook references  Lecture slides 
1  Feb 21  Administratrivia. Some mathematical preliminaries. The Halting Problem. Finite automata. Regular languages. Closure properties: Union. 
Chapter 0. Chapter 1, Section 1.1.  D 1 
2  Feb 28  NonRegular Languages. Pumping Lemma. NonDeterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata via generalized NFAs.  Chapter 1, Sections 1.11.4.  D 2 
3  Mar 7  Closure properties of regular languages. Regular expressions and their equivalence with finite automata. Decision problems for finite automata. Transducers. Linear Grammars. Introduction to context free grammars. 
Chapter 1, 2.1  
4  Mar 14  Context free grammars. Pumping lemma for context free grammars. Examples for non context free languages. Push down automata (nondeterministic and deterministic). The equivalence theorem: CFL vs. PDAs (without proof). 
Sipser, Chapter 2  M4 Alice&Bob 
5  Mar 21  Closure properties of CFLs. Algorithmic properties about CFLs. Chomsky normal form of a CFG.  Sipser, Sections 2.1, 2.2, 2.3. Hopcroft and Ullman, Sections 4.5, 4.7, 5.3, 6.2, 6.3.  CFL intersect REG 
6  Mar 28  What is a computation. Turing's analysis. Turing Machines. The language classes R, RE. 
Sipser, Chapter 3.  Lecture 6 
7  April 4  ktapes Turing Machines, Nondeterministic TM, Counter Machines, RAM machines, Simulation of TMs in Scheme, Diagonalization, ChurchTuring thesis 
on decidability. tm.txt. 

8  April 11  Why finite problems are decidable; Interpreters; Steppers; doing things in parallel; undecidability: universal halting, A_TM, Empty; Turing reductions; Rice Theorem  New Lecture 8.  
9  May 2  Steppers, Computational Histories, Rice Theorem, Equivalence of programs and of terminating programs, Oracles, Undecidability of CFG fullness, R.E. is the class of all enumerable languages (see attached program). 
New Lecture 9. enumerator. 

10  May 16  Basic time complexity classes, P, NP, Verifiers, The time hierarchy n n^2 n^4…  Lecture 10.  
11  May 23  Sudoku is NP, Reduction from Sudoku to SAT, CookLevin Thm, NPcompleteness, 3SAT, Clique  Lecture 11.  
12  May 30  Subset sum, integer programming. Unrestricted grammars. Hilbert's 10th problem, Quantified real polynomials is decidable, QBF harder than SAT, Post Correspondence and tiling, Kolmogorov complexity. 
Lecture 12.  
13  June 6  Final Topics  New Lecture 14 Final Topics 