CSE 322 Introduction to Formal Models in Computer Science, Spring 2009
Meets: Monday, Wednesday, and Friday 1:30-2:20pm in 153 Mueller Hall
|
|
|
Office Hours |
Location |
Phone |
| Instructor: |
Dave Bacon |
dabacon at cs |
Monday 2:30-3:00
Wednesday 11-12:30
Friday, 12:30-1:30 |
CSE 460 |
221-6503 |
| TAs: |
Ioannis Giotis |
giotis at cs |
Thursday 11-12 |
CSE 218 |
|
|
Deepak Verma |
deepak at cs |
Thursday 1-2 |
CSE 220 |
|
Final: Monday, June 8, 2:30-4:30pm in class, 153 Mueller Hall. Closed notes. There will be a review session on Saturday, June 6, 1-2pm in EEB 045.
Midterm: Wednesday, May 6, in class. Closed notes. There will be a midterm review session on Monday, May 4, 600-730pm in EEB 045.
Textbook: Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, Second Edition. First edition is also okay. International edition may cause problems since the problem numbers won't be properly listed on homeworks. (Second edition errata: first printing. First edition errata: first printing , later printings .)
Class Mailing List: You are responsible for signing up for and keeping up to date with the class mailing list. Subscribe here. Post your questions or comments here as well.
Feedback: Can be provided anonymously via this form.
Grading: Homework: 60%, Midterm: 15%, Final: 25%
Collaboration/Cheating Policy: See here.
Calendar:
| Week |
Monday |
Wednesday |
Friday |
1
Reading:
0.1-0.4,1.1
|
Mar. 30 |
Lecture 1
Welcome and Introduction |
Apr. 1 |
Lecture 2
Finite Automata |
Apr. 3 |
Lecture 3
Finite Automata
Regular operations
Formal definition
|
2
Reading: 1.2
|
Apr. 6 |
Lecture 4
Nondeterministic Finite Automata
|
Apr. 8 |
Lecture 5
Equivalence Between NFA and DFA
|
Apr. 10 |
Lecture 6
Closure Properties of FA
Homework 1 due! |
3
Reading: 1.3
|
Apr. 13 |
Lecture 7
Regular expressions
|
Apr. 15 |
Lecture 8
Regular expressions and DFAs |
Apr. 17 |
Lecture 9
Regular expressions and DFAs
Homework 2 due! |
4
Reading: 1.4
|
Apr. 20 |
Lecture 10
Pumping Lemma for DFAs
| Apr. 22 |
Lecture 11
Pumping Lemma for DFAs
|
Apr. 24 |
Lecture 12
Myhill-Nerode
Homework 3 due! |
5
Reading: 2.1
|
Apr. 27 |
Lecture 13
Myhill–Nerode Theorem
|
Apr. 29 |
Lecture 14
DFA Minimization/Pattern Matching
|
May 1 |
Lecture 15
Pattern Matching
Homework 4 due!
|
6
Reading: 2.1
|
May 4 |
Introduction to Context Free Languages
|
May 6 |
Lecture 16
Midterm In Class! |
May 8 |
Lecture 17
Ambiguity in CFGs
|
7
Reading: 2.2
|
May 11 |
Lecture 18
Chomsky Normal Form
|
May 13 |
Lecture 19
Pushdown Automata
|
May 15 |
Lecture 20
Pushdown Automata
Homework 5 due!
|
8
Reading: 2.3
|
May 18 |
Lecture 21
CFG and PDAs |
May 20 |
Lecture 22
Closure Properties of CFLs
|
May 22 |
Lecture 23
Pumping lemma for CFLs
|
9
Reading: 3.1 and 3.2
|
May 25 |
Holiday! No Class! |
May 27 |
Lecture 24
Pumping lemma for CFLs
Homework 6 due! |
May 29 |
Lecture 25
Cocke-Younger-Kasam |
10
Reading: 4.1 and 4.2
|
June 1 |
Lecture 26
Turing Machines
| June 3 |
Lecture 27
Decidability
|
June 5 |
Lecture 28
The Halting Problem
Homework 7 due! |
11
|
June 8 |
Final Exam |
|
|
|
|
|
CSE Home 
