Course Schedule

Weekday Regular Schedule

Group Type Hours Location
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.

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.

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
S 1;
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.
S 2;
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.
S 3;
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
S 4;
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
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, Myhill-Nerode, Turing Machine
S 6;
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
ham-reduction.
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 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
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 k-tapes Turing Machines, Non-deterministic TM,
Counter Machines, RAM machines,
Simulation of TMs in Scheme,
Diagonalization, Church-Turing 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, Cook-Levin Thm, NP-completeness, 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
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License