CS 373: Lecture Schedule

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 8/23 Administrivia, overview,
motivation		   slides#1 Chapter 0    
2 8/25 Math preliminaries; Sets, countable and uncountable sets, strings and languages, uncomputable language exist
countability/uncountability
undecidable lang exist		 Lecture Notes #2 slides#2 Chapter 0 of Sipser
Read Chap.1,2,3 of
Discrete Mathematics, by Chen
   
3 8/30 Languages, machines,
deterministic finite automata		 Lecture Notes #3 slides#3 Chapter 1.1 of Sipser    
4 9/1 Product Construction; Intersction
and Union of Regular Languages		 Lecture Notes #4 slides#4 Chapter 1.1 of Sipser    
5 9/6 Closure of reg lang under complement; Nondet finite automata Lecture Notes #5 slides#5 Chapter 1.2 of Sipser    
6 9/8 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.  
7 9/13 Equivalence of RegExp and NFAs Lecture Notes #7 slides#7 Chapter 1.3 of Sipser    
8 9/15 Equivalence of NFAs and DFAs Lecture Notes #8 slides#8 Chapter 1.2 of Sipser    
9 9/20 DFAs to regular expressions; Suffix languages and characterizing regular languages Lecture Notes #9 slides#9 Read lecture notes or book by Hoproft-Ullman   Video
10 09/22 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 09/27 Proving non-regularity using MNT and PL Same as Lec 10 slides#11 Not in Sipser; read lecture notes   Video
12 09/29 Algorithms on DFAs (emptiness, inclusion, minimization, etc.) Lecture Notes #11 slides#12 Not in Sipser; read lecture notes   Video
-- 10/4 Review session -- slides#13     Video
13 10/6 Turing machines: Turing, Hilbert, and definition of TMs Lecture Notes #12 slides#14 Sipser 3.1, 3.2   Video
14 10/11 Turing machines (contd.) Lecture Notes #13 slides#14 Sipser 3.1, 3.2   Video
15 10/13 Turing machines: More algorithms, Variants, Robustness, Encodings Lecture Notes #14 slides#15 Sipser 3.1, 3.2   Video
16 10/18 Simulating "real" computers, Universal Turing machines Lecture Notes #15 slides#16 Sipser 3.1, 3.2; also 4.1   Video
17 10/20 Undecidable languages Lecture Notes #16 slides#17 Sipser 4.2   Video 
18 10/25 Decidable and Recognizable languages; Closure properties; Reductions See also lec#16 notes
Lecture Notes #17		 slides#18 Sipser 5.1   Video
19 10/27 More Reductions; Rice's theorem Lecture Notes #18 slides#19 Sipser 5.1   Video
20 11/1 More on Rice's theorem; more undecidability; dovetailing See lec 18 notes slides#20 Sipser 5.1   Video
21 11/3 Dovetailing, Non-deterministic TM's Lecture Notes #19 slides#21 Sipser 5.1   Video
22 11/8 Context-free languages, context-free languages, parse-trees Lecture Notes #20 Sipser 2   Video
23 11/10 Review Session -- -- Sipser 2.1   Video
24 11/15 Chomsky Normal Form Lecture Notes #21 Sipser 2.1   Video
25 11/17 Decidable membership; CYK algorithm; CFLs closed intersection with regular languages Lecture Notes #22 Sipser 2.1   Video
26 11/29 Pumping lemma for CFLs, non-context-free languages, and non-closure under intersection and complement, pushdown automata Lecture Notes #23 and Lecture Notes #24 Sipser 2.1, 2.2   Video
27 12/1 Complexity theory: P and NP; NP-completeness, Cook's theorem, reductions No Lecture Notes
See Sipser		 Sipser 7   Video

Tentative schedule for future lectures

Lecture
Number		 Date Material covered Lecture
notes		 Lecture screen capture Readings/Handouts
/Hyperlinks		 Comments Video
27 Recap of course   Slides      
**NEW** Review of most material in the course.