Course Schedule

Weekday Regular Schedule

Group Type Hours Location
08 Lecture Wed 10-13 Dan-David 001
09 Recitation Thu 12-13 Orenstain 103
10 Recitation Thu 14-15 Orenstain 111
11 Lecture Mon 13-16 Dah 005
12 Recitation Wed 15-16 Schriber 006
13 Recitation Wed 14-15 Schriber 006
14 Recitation Thu 13-14 Dan David 111

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. 17 & 19 Administratrivia. Some mathematical preliminaries. Finite automata. Regular languages. Closure properties: Union. Chapter 0. Chapter 1, Section 1.1. Intro;

Lecture 1;

2 Feb. 24 & 26 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 3 & 5 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 10 & 12 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;
5 March 17 & 19 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;
6 March 24 & 26 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 March 31 & April 2 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 April 7 & 23 Mapping reductions. More undecidable languages. Rice theorem. Sipser, Sections 5.1, 5.3. Lecture 8.
9 April 28 & 30 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 and Recitation 9.
10 May 12 & 14 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 May 19 & 21 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 May 26 & 28 Additional poly time reductions. Sipser, sections 7.5. Lecture 12
and
3SAT to Hamiltonian-Path—]
13 June 9 & 11 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 2013 course page

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