Course Schedule

Weekday Regular Schedule

Group Type Hours Location
05 Lecture Wed 10-13 Rosenblatt - Software Engineering 102
06 Recitation Thu 12-13 Schreiber 06
07 Recitation Thu 14-15 Kaplun 118
08 Recitation Thu 14-15 Software Engineering 104
09 Lecture Mon 13-16 Dan-David 01
10 Recitation Wed 15-16 Orenstein 103
11 Recitation Wed 14-15 Orenstein 103
12 Recitation Thu 13-14 Kaplun 118
13 Recitation Thu 12-13 Orenstein 111

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 Groups 10,11 Groups 6-8,12,13
1 February 29 & March 2 Administratrivia. Introduction. Finite automata. Regular languages. Closure properties: Union. Chapter 1, Section 1.1.

Intro

Lecture 1

Recitation 1 Wed. March 2nd Thu. March 3rd
2 March 7 & 9 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 Wed. March 9th Thu. March 10th
3 March 14 & 16

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

Wed. March 16th Thu. March 17th
4 March 21 & 23

Context free languages. Context free grammars.

Sipser, Section 2.1

Lecture 4

Recitation 4

Wed. March 23rd Fri. March 25th
5 March 28 & 30

Algorithmic properties of CFLs. Chomsky normal form of a CFG. Pumping lemma for CFGs. Push Down Automata.

Sipser, Sections 2.1, 2.2, 2.3.

Lecture 5

Recitation 5 Wed. March 30th Thu. March 31st
6 April 4 & 6 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 Wed. April 6th Thu. April 7th
7 April 11 & 13

Turing Machines, Formal definition, Multi-tape TMs, RAMs, Church-Turing thesis

Sipser, Sections 3.1,3.2,3.3

Lecture 7

Recitation 7 Wed. April 13th Thu. April 14th
8 April 18 & May 2 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 Mon. April 18th Tue. April 19th
9 May 4 & 9

Mapping reductions. More undecidable languages. Rice theorem.

Sipser, Sections 5.1, 5.3.

Lecture 9

Recitation 9 Wed. May 4th Thu. May 5th
10 May 16 & 18

Mapping reductions. Rice theorem. Reductions using controlled executions. Reductions using computation histories. RE Completeness.

Sipser, Sections 5.1, 5.3.

Lecture 10 Recitation 10 Wed. May 18th Thu. May 19th
11 May 23 & 25

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 Wed. May 25th Fri. May 20th
12 May 30 & June 1 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 Wed. June 1st Thu. June 2nd
13 June 6 & 8

NP-completeness of SAT, 3SAT.

Sipser, chapter 7.4 and 7.5.

Lecture 13

Recitation 13 Wed. June 8th Thu. June 9th

Previous Year's Course and Videos

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