This is a preliminary outline of lecture topics and corresponding readings from the textbook. As the term progresses, we will update it for what we actually covered and add links to the handouts and slides from lecture. Video links to the lectures will be provided, on purpose, late, usually *after* the homework for the material covered in the lecture has been handed back. The idea is to encourage students to come to the lecture and yet have the video available so that they can review the material for better understanding, especially for exams.

Lecture notes are intended only to show what topics were covered, so you can find and read the corresponding sections in the textbook. They are not intended to be a substitute for the textbook and handouts.

Lecture Number |
Date | Material covered | Lecture notes |
Lecture screen capture | Readings/Handouts /Hyperlinks |
Comments | Video |
---|---|---|---|---|---|---|---|

1 | 1/20 | Administrivia, overview, motivation |
slides#1 | Chapter 0 | Video | ||

2 | 1/21 | Discrete math; Strings and languages countability/uncountability undecidable lang exist |
Lecture Notes #2 | slides#2 | Chapter0 of Sipser Read Chap.1,2,3 of Discrete Mathematics, by Chen |
Video | |

3 | 1/26 | Languages, machines, deterministic finite automata |
Lecture Notes #3 | slides#3 | Chapter 1.1 of Sipser | JFLAP is a tool to manipulate automata Check it out www.jflap.org |
Video |

4 | 1/28 | Product Construction; Intersction and Union of Regular Languages |
Lecture Notes #4 | slides#4 | Chapter 1.1 of Sipser | Video | |

5 | 2/2 | Closure of reg lang under complement; Nondet finite automata | Lecture Notes #5 | slides#5 | Chapter 1.2 of Sipser | Video | |

6 | 2/4 | Closure of reg lang under concat, Kleene-*, reversal |
Lecture Notes #6 | slides#6 | Chapter 1.2 of Sipser | Read formal proof of the constructions in the lecture notes. | Video |

7 | 2/9 | Equivalence of NFAs and DFAs | Lecture Notes #7 | slides#7
Errata |
Chapter 1.2 of Sipser | Video | |

8 | 2/11 | Equivalence of RegExp and NFAs | Lecture Notes #8 | No slides! See Video! | Chapter 1.3 of Sipser | Video | |

9 | 2/16 | Suffix languages; DFA minimization; Myhill-Nerode theorem; | Lecture Notes #9 | slides#9 | Read lecture notes or book by Hoproft-Ullman | Video | |

10 | 2/18 | Proving non-regularity using Myhill-Nerode thm and the pumping lemma | Lecture Notes #10 | slides#10 | Read lecture notes for MNT technique; read Sipser/lecture notes for Pumping Lemma | Video | |

11 | 2/23 | Algorithms on DFAs (emptiness, infiniteness, minimization, etc.) | Lecture Notes #11 | slides#11 | Not in Sipser; read lecture notes | Video | |

2/25 | NO LECTURE - Midterm in the evening |
Video | |||||

12 | 3/2 | Turing machines (Hilbert, Godel, Church, Turing and the Church-Turing hypothesis) | Lecture Notes #12 | slides#12 | Sipser 3.1 | Video | |

13 | 3/4 | Turing machines: more examples, and variants | Lecture Notes #13 | slides#13 | Sipser 3.1, 3.2 | Video | |

14 | 3/9 | More decidable problems, encodings, simulating "real" computers, recognizability vs decidability | Lecture Notes #14 | slides#14 | Sipser 3.1, 3.2; also 4.1 | Video | |

15 | 3/11 | Closure properties of decidable and recognizable languages under union, intersection, complement, etc., Universal Turing machines | Lecture Notes #15 | Slides lost- computer crash! | Sipser 4.2 | Video | |

16 | 3/16 | Undecidable languages | Lecture Notes #16 | slides#16 | Sipser 4.2 | Video | |

17 | 3/18 | Reductions | Lecture Notes #17 | slides#17 | Sipser 5.1 | Video | |

3/23 | Fighting and waiting through crowded airports Driving cars and planes controlled by Turing machines |
||||||

3/25 | Playing in the sun having fun | ||||||

18 | 3/30 | Rice's theorem: Nothing about a TM's language is decidable! | Lecture Notes #18 | Slides | Sipser 5.1 | Video | |

4/1 | Review session; NO LECTURE | Sipser 5.1 | |||||

4/5 | MIDTERM 2 |
Sipser 5.1 | |||||

19 | 4/6 | Dovetailing, Enumeration and recognizability, Non-deterministic TM's | Lecture Notes #19 | Slides | Sipser 5.1 | Video | |

20 | 4/8 | Context-free languages, context-free languages, parse-trees | Lecture Notes #20 | Slides | Sipser 2 | Video | |

21 | 4/13 | Chomsky Normal Form | Lecture Notes #21 | Slides | Sipser 2 | Video | |

22 | 4/15 | Decidable membership; CYK algorithm; CFLs closed intersection with regular languages | Lecture Notes #22 | Slides | Sipser 2 | Video | |

23 | 4/20 | Pumping lemma for CFLs, non-context-free languages, and non-closure under intersection and complement | Lecture Notes #23 | Slides | Sipser 2 | Video | |

24 | 4/22 | Recursive automata, pushdown automata, and CFLs | Lecture Notes #24 | Slides | Sipser 2 | Video | |

25 | 4/27 | Complexity theory; P and NP | No Lecture Notes See Sipser |
Slides | Sipser 7 | Video | |

26 | 4/29 | Complexity theory: NP-completeness, Cook's theorem, reductions | No Lecture Notes See Sipser |
Slides | Sipser 7 | Video | |

27 | 5/4 | Recap of course | Slides | Video |

Review of most material in the course.