NOTES: Chapters from Sipser's book are indicated by "Sipser X.Xquot;. Material from my book will be indicated by "Yap X"

SCHEDULE OF LECTURES (non-binding)
No. DATE LECTURE REMARKS/READING
1 Jan 21 Introduction; DFA & NFA First Class, Sipser 1.1, 1.2
2   26 Regular Expressions Sipser 1.3
3   28 Regular Pumping Lemma Sipser 1.4
4 Feb 2 CFG & PDA Sipser 2.1, 2.2
5   4 Pumping Lemma Sipser 2.3
6   9 Turing Machines Sipser 3
7   11 Decidable Problems Sipser 4.1
--   16 -- President's Day
8   18 Halting Problem Sipser 4.2
9   23 Reducibility Sipser 5.1 (omit 5.2)
10   25 Recursion Theorem Sipser 6.1
11 Mar 2 Logical Theories Sipser 6.2
12   4 Descriptive Complexity Sipser 6.4 (omit 6.23)
13   9 MIDTERM  
14   11 Intro to Complexity Classes Yap 1
--   16 SPRING BREAK  
15   23 Basic Relationships, Basic Classes Yap 2
16   25 Polynomial Reducibilities Yap 4
17   30 Complete Languages Yap 5
18 Apr 1 Alternating Machines I Yap 7, Sipser 10.3
19   6 Alternating Machines II  
20   8 Probabilistic Machines I Yap 8, Sipser 10.2
21   13 Probabilistic Machines II  
22   15 Interactive Proofs I Sipser 10.4
23   20 Interactive Proofs II  
24   22 Circuit Complexity I Yap 10, Sipser 9.3
25   27 Circuit Complexity II  
26   29 Open  
27 May 4 Open  
--   6   FINAL EXAM WEEK