Course Schedule

Table of Contents

# Weekday Regular Schedule

Group | Type | Hours | Location |
---|---|---|---|

01 | Lecture | Mon 13-16 | Dan-David 003 |

02 | Recitation | Wed 13-14 | Dan-David 203 |

03 | Recitation | Wed 14-15 | Dan-David 205 |

04 | Recitation | Wed 15-16 | Dan-David 003 |

# Course Plan

The course roughly consists of three parts:

- Lectures 1-5: languages and automata theory.
- Lectures 6-10: computability theory.
- Lectures 11-13: complexity theory.

# Detailed Schedule

Lecture | Date | Lecture topics | Textbook references | Lecture slides | Recitation slides |

1 | Oct. 27 | Administratrivia. Some mathematical preliminaries. Finite automata. Regular languages. Closure properties: Union. | Chapter 0. Chapter 1, Section 1.1. | Intro; Lecture 1; Python code for DFA class; (Lecture 1 and code updated Oct. 28) |
Recitation 1; |

2 | Nov. 3 | 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; NFA- eliminating epsilon moves; |

3 | November 10 | 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; | Recitation 3; |

4 | November 17 | Context free grammars and languages. Examples of context free languages and parse trees. Ambiguity. Pumping lemma for context free grammars. Examples for non context free languages. Push down automata (non-deterministic and deterministic). | Sipser, Sections 2.1, 2.2, 2.3. | Lecture 4; | Recitation 4; |

5 | November 24 | Push down automata (reminder). Closure properties of CFLs. Non-determinism adds power to PDAs. Algorithmic questions about CFLs. The equivalence theorem: CFLs vs. PDAs. Chomsky normal form of a CFG. | Sipser, Sections 2.1, 2.2, 2.3. | Lecture 5; (updated Nov. 25) |
Recitation 5; |

6 | December 1 | Turing Machines. Alternative Models of Computers: Multi tape TMs, RAMs, Non Deterministic TMs. The Church-Turing thesis. The language classes R, RE and coRE. |
Sipser, Sections 3.1, 3.2. | Lecture 6; | Recitation 6; |

7 | December 8 | Church-Turing thesis (reminder). Encoding of Turing Machines. The universal TM. The halting / acceptance problems are undecidable. | Sipser, Sections 3.2, 3.3, 4.1, 4.2. | Lecture 7; | Recitation 7; |

8 | December 15 | Hilbert's 10th problem. Reductions. The halting problem in a Pythonic skin. Mapping reductions. More undecidable languages. The busy beaver problem. Rice theorem. | Sipser, Sections 5.1, 5.3. | Lecture 8 (updated Dec. 21: slides 51-53). | Recitation 8; (updated Dec. 17 - after recitation) |

9 | December 22 | Mapping reductions. Rice theorem. Reductions using controlled executions. RE Completeness. Reductions using computation histories. Linear Bounded Automata. Tiling. Unrestricted grammars. |
Sipser, Sections 5.1, 5.3. | Lecture 9 | Recitation 9; |

10 | December 29 | Tiling. Unrestricted grammars. Deterministic and non-deterministic time classes. The classes P and NP and examples of languages in each. |
Sipser, Sections 7.1. - 7.3 | Lecture 10. | Recitation 10; |

11 | January 5 | Deterministic and non-deterministic time classes. The classes P and NP and examples of languages in each. Polynomial verifiability and the class NP. The class coNP. | Sipser, chapter 7.4 and 7.5 | Lecture 11; Lecture covered sections 1 to 5 (including) only. | Recitation 11; |

12 | January 12 | Additional poly time reductions: 3SAT, clique, Hamiltonian path, graph 3 colorability, integer programming. | Sipser, sections 7.5. | Lecture 12 (revised Jan. 16) and 3SAT to Hamiltonian-Path—] |
Recitation 12; |

13 | January 19 | Additional poly time reductions: Integer programming, Subset Sum. NP hardness and co-NP hardness. Proof of Cook-Levin theorem: CSAT is NP complete. Decision, search, and optimization problems. Interactive proofs. Concluding remarks. | Sipser, chapters 9.1 and 10.1-10.2. | Lecture 13 | Recitation 13; |

# Previous Year's Course and Videos

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).