Course Schedule

Weekday Regular Schedule

Group Type Hours Location
01 Lecture Mon 13-16 Dan-David 003
02 Recitation Wed 15-16 Dan-David 207
03 Recitation Wed 14-15 Dan-David 207
04 Recitation Thu 13-14 Dan-David 205

Course Plan

The course roughly consists of four parts:

  1. Lectures 1-3: Languages and automata theory: Regular languages.
  2. Lectures 4-6: Languages and automata theory: Context-free languages.
  3. Lectures 7-10: Computability theory.
  4. Lectures 11-13: Introduction to complexity theory.

Detailed Schedule

Lecture Date Lecture topics Textbook references Lecture slides Recitation notes
1 Oct. 31 Administratrivia. Introduction. Finite automata. Regular languages. Closure properties: Union. Chapter 1, Section 1.1.

Intro

Lecture 1

Recitation 1

2 Nov. 7 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

Recitation 2

3 Nov. 14 Two approaches for proving a language is non-regular: (1) Myhill-Nerode theorem (2) the pumping lemma. Computational questions stemming from finite automata. Sipser, Sections 1.4, 2.1-2.2. Hopcroft and Ullman, Section 3.4. Lecture 3

Recitation 3

4 Nov. 21 Context free languages. Sipser, Section 2.1 Lecture 4

Recitation 4

5 Nov. 28 Chomsky normal form of a CFG. Checking Membership. Pumping lemma for CFGs. Push Down Automata. Sipser, Sections 2.1, 2.2, 2.3. Lecture 5

Recitation 5

6 Dec. 5 More on CFLs and PDAs: Non-determinism adds power to PDAs. Non determinism vs. ambiguity in CFLs. Closure properties of CFLs. Algorithmic properties about CFLs. The equivalence theorem: CFLs vs. PDAs. Sipser, Sections 2.1, 2.2, 2.3. Lecture 6

Recitation 6

7 Dec. 12 Turing Machines, Formal definition, Multi-tape TMs, RAMs, Church-Turing thesis Sipser, Sections 3.1,3.2,3.3 Lecture 7

Recitation 7

8 Dec. 19 Non-Deterministic TMs. Encoding of TMs. A universal TM. The Halting /Acceptance problems are undecidable. Sipser, Sections 3.2, 3.3, 4.1, 4.2. Lecture 8

Recitation 8

9 Dec. 29 Mapping reductions. Sipser, Sections 5.1, 5.3. Lecture 9

Recitation 9

10 Jan. 2 Rice theorem and friends. Reductions using controlled executions and computation histories. Linear Bounded Automata. RE Completeness. Sipser, Sections 5.1, 5.3. Lecture 10

Recitation 10

11 Jan. 9 Deterministic and non-deterministic time classes. A time lower bound. The classes P and NP and examples of languages in each. The class coNP. Verifiability. Sipser, Sections 7.1. - 7.3 Lecture 11

Recitation 11

12 Jan. 16 The classes P and NP and examples of languages in each. Verifiability. The class coNP. NP-completeness. Polynomial time reductions. Sipser, chapter 7.4 and 7.5 Lecture 12

Recitation 12

13 Jan. 23 NP-completeness of SAT, CLIQUE, INDSET, Hamiltonian Path. Sipser, chapter 7.4 and 7.5. Lecture 13
and
3SAT to Hamiltonian-Path

Recitation 13

Previous Year's Course and Videos

Spring 2016 course page

Spring 2015 course page

Spring 2014 course page

Spring 2013 course page - 2013's recitations (by Oren Salzman) were filmed and are available here.

Spring 2012 course page

Spring 2011 course page

Spring 2009 course page - This also contains links to videos of almost all classes (by Benny Chor) and recitations (by Rani Hod).

Filmed lectures and recitations 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