Week 1: Introduction to CSE 355;
1/15;1/17 Value of this class to any programmer
Proof techniques
(showing equivalence of sets;
logical connectives; induction)
Chapter 1 of text book;
Chapter 0 of Sipser's book;
Chapter 1 of Sudkamp's book.
Week 2: Proof by contradiction;
1/22;1/24 I don't know, I don't care proof;
total, 1-1, onto; cardinality;
Natural vs Even;
N vs N X N;
N vs R01 (Cantor's diagonalization)
Chapter 1 of text book;
Chapter 0 of Sipser's book;
Chapter 1 of Sudkamp's book.
Week 3: alphabet, strings, langauge etc. (Chapter 1.5)
1/29;1/31 introduction to languages (regular, CF, CS etc.)
DFA (2 examples) (Chapter 2.2)
DFA (delta, delta hat)
Week 4: NFA (definition, delta, delta hat) (Chapter 2.3)
2/5;2/7 NFA --> DFA
string searching application (Chapter 2.4)
epsilon-NFA (Chapter 2.5)
Week 5: Regular expression (Chapter 3.1)
2/12;2/14 English description --> regular expression
Regular expression to epsilon-NFA (Chapter 3.2.3)
DFA to regular expression (Chapter 3.2.2)
mention pumping lemma (Chapter 4.1)
(Chapter 1.3 of Sipser's book)
Week 6: Pumping Lemma (Chapter 4.1)
2/19;2/21 Some properties of regular languages (Chapter 4.2.1)
Week 7: More pumping lemma; Closure properties (Chapters 4.2.2; 4.3)
2/26;2/28 Review for test (4.2.1, 4.2.2 & 4.3 not on test 1)
Test 1 on 2/28
Test 1 content:
Ch1 Review; proof techniques
(equivalence of sets; proof by induction;
countable and uncountable sets; diagonalization;
don't know don't care proof) -- (20 - 25%)
Section 1.5, Ch 2 (2.2; 2.3; 2.4; 2.5) -- (25 - 30%)
Ch 3 (3.1; 3.2.2; 3.2.3) -- (25 - 30%)
Ch 4 (4.1) -- (25 - 30%)
Week 8
3/4; 3/6 Equivalence and minimization (Chapters 4.4.2, 4.4.3)
Context free grammars; parse trees (5.1, 5.2.1-5.2.3, 5.3, 5.4.1)
SPRING BREAK
Week 9 Pushdown automata (Chapters 6.1, 6.2.1, 6.2.2)
3/18;3/20
Week 10 CFG --> PDA (Chapter 6.3.1)
3/25; 3/27 DPDA (Chapter 6.4)
CFG --> CNF (Chapter 7.1, not on Test 2)
Pumping lemma for CFG (Chapter 7.2)
Week 11 Pumping lemma for CFG (Chapter 7.2)
4/1; 4/3 Review
Test 2 on 4/3
Chapter 4 (4.2.1; 4.2.2; 4.3; 4.4.2; 4.4.3) -- (15 - 20%)
Chapter 5 (5.1; 5.2.1; 5.2.2; 5.2.3; 5.3; 5.4.1) -- (25 - 35%)
Chapter 6 (6.1; 6.2.1; 6.2.2; 6.3.1; 6.4) -- (30 - 35%)
Chapter 7 (7.2) -- (20 - 30%)
Week 12 Closure properties of CFL (7.3.2-7.3.4, 7.4)
4/8;4/10 Problems for which programs do not exist
Week 13 Turing Machine (Chapter 8.2)
4/15;4/17 Halt etc. (Handout 1)
Week 14 NP-Completeness (Handout 2)
4/22;4/24 Review
Week 15 Test 3 on 4/29
4/29 (last day of class)
Chapter 7 (7.1; 7.3.2; 7.3.3; 7.3.4; 7.4) -- (30 - 35%)
Chapter 8 (8.2) -- (20 - 25%)
Chapter 9 (Handout 1) -- (15 - 20%)
Chapter 10(Handout 2) -- (20 - 25%)
Finals: Either a comprehensive final or an optional final
5/1 12:20 PM to 2:10 PM