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