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 |