Weekday Regular Schedule
|08||Lecture||Wed 10-13||Dan-David 001|
|09||Recitation||Thu 12-13||Shenkar 222|
|10||Recitation||Thu 14-15||Melamed 007|
|11||Lecture||Mon 13-16||Dan-David 001|
|12||Recitation||Wed 15-16||Shenkar 222|
|13||Recitation||Wed 14-15||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.
The course roughly consists of three parts:
- Lectures 1-5: languages and automata theory.
- Lectures 6-10: computability theory.
- Lectures 11-13: complexity theory.
Group 08 Time-Table (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
|Chapter 0. Chapter 1, Section 1.1.||M 1 intro; M 1 DFA;|
|2||Mar 2||Non-Deterministic Finite Automata (NFA). Closure properties of Regular Languages. Regular expressions and their equivalence with finite automata via generalized NFAs.||NFAs. Regular expressions.
|Chapter 1, Sections 1.1-1.3.||M 2;|
|3||Mar 9||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.||The pumping lemma for regular languages, Homomorphism.
|Sipser, Sections 1.4, 2.1-2.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 (non-deterministic and deterministic). The equivalence theorem: CFL vs. PDAs. Examples of languages accepted by PDAs.||Writing context-free grammars. Pumping lemma for CFLs
|Sipser, Sections 2.1, 2.2, 2.3.||New Lectures 4 and 5.|
|5||Mar 23||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.||Closure properties for CFLs. PDAs
|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, Myhill-Nerode, Turing Machine
|Sipser, Sections 3.1, 3.2.||New Lecture 6.|
|7||April 6||Church-Turing 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 non-deterministic 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). Poly-time 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
|14||June 1||Optimization, search, and decision problems. Approximate solutions to optimization problems.||More poly time reductions||Sipser, chapter 10.||New Lecture 14|
Group 11 Time-Table (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||Non-Regular Languages. Pumping Lemma. 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.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 (non-deterministic and deterministic). The equivalence theorem: CFL vs. PDAs (without proof).
|Sipser, Chapter 2||M4
|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.
The language classes R, RE.
|Sipser, Chapter 3.||Lecture 6|
|7||April 4||k-tapes Turing Machines, Non-deterministic TM,
Counter Machines, RAM machines,
Simulation of TMs in Scheme,
Diagonalization, Church-Turing thesis
|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.
|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, Cook-Levin Thm, NP-completeness, 3SAT, Clique||Lecture 11.|
|12||May 30||Subset sum, integer programming.
Hilbert's 10th problem, Quantified real polynomials is decidable, QBF harder than SAT, Post Correspondence and tiling, Kolmogorov complexity.
|13||June 6||Final Topics||New Lecture 14