Steam-powered Turing Machine University of Washington Computer Science & Engineering
 CSE 322 Introduction to Formal Models in Computer Science, Spring 2008
  CSE Home     CSE 322  About Us    Search    Contact Info 

Class Communication
 Anonymous Comment Form
 Class Mailing List
 Mailing List Archive
 Assignment #1
 Assignment #2
 Assignment #3
 Assignment #4
 Assignment #5
 Assignment #6
 Assignment #7
 Extra credit
Lecture Notes
 DFA Formal Definition
 Regular Operations
 Nondeterministic Finite Automata
 NFA to DFA construction
 Closure of Regular Operations
 Regular Expressions
 DFA to Regular Expression
 Pumping Lemma
 String Matching
 Myhill-Nerode Theorem
 Minimizing DFAs
 Intro to Context Free Grammars
 Chomsky Normal Form
 Pushdown Automata
 PDAs and CFGs
 Closures for CFLs
 Pumping Lemma for CFLs
 Turing Machines
 Midterm topics
 Sample Midterm I (Beame)
 Sample Midterm II (Rao)
 Sample Midterm II Sols (Rao)
 Midterm Sols
 Final topics
 Sample Final (Beame)
 Sample Final Sols (Beame)
Handouts/Other Notes
 Seattle Game State Diagram
 Defining Delta Star (Beame)
 Myhill-Nerode Theoerem (Beame)
 DFA Minimization (Beame)
 Closure for CFLs (Hopcroft et al)
 CKY Algorithm (Beame)
 Standard Syllabus
 This Quarters Syllabus
 Collaboration & Homework Policy

CSE 322 Introduction to Formal Models in Computer Science, Spring 2008

Meets: Monday, Wednesday, and Friday 1:30-2:20pm in EEB 045

Office Hours Location Phone
Instructor: Dave Bacon   dabacon at cs  
Mondays 2:30-3:00
Wednesdays 2:30-4:00
Friday 12:00-1:00
or by appointment
CSE 460 221-6503
TAs: Hao Lu    hlv at cs   Thursdays 5:00-6:00 CSE 216
Isaac Myers   eyezac at cs   Thursdays 11:30-12:30 CSE 216

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: 55%, Midterm: 20%, Final: 25%

Collaboration/Cheating Policy: See here.

Final Review: Thursday, June 5, 5:30-7:30pm in EEB 125


Week Monday Wednesday Friday
Mar. 31 Lecture 1
Welcome and Introduction
Apr. 2 Lecture 2
Finite Automata
Formal definition
Apr. 4 Lecture 3
Finite Automata
Regular operations
Reading: 1.2

Apr. 7 Lecture 4
Nondeterministic Finite Automata
Apr. 9 Lecture 4
Equivalence Between NFA and DFA
Apr. 11 Lecture 5
Closure Properties of FA
Homework 1 due
Reading: 1.3

Apr. 14 Lecture 6
Regular expressions
Apr. 16 Lecture 7
Regular expressions and DFAs
Apr. 18 Lecture 8
Regular expressions and DFAs
Homework 2 due
Reading: 1.4

Apr. 21 Lecture 9
Pumpling Lemma for DFAs
Apr. 23 Lecture 10
Pattern Matching
Apr. 25 Lecture 11
Myhill–Nerode Theorem
Homework 3 due
Reading: 2.1

Apr. 28 Lecture 12
Apr. 30 Lecture 13
DFA Minimization/Introduction to Context Free Languages
May 2 Lecture 14
Context Free Languages

Reading: 2.1

May 5 Lecture 15
Ambiguity in CFGs
Homework 4 due
May 7 Lecture 16
Chomsky Normal Form
May 9 Midterm in class!
Reading: 2.2

May 12 Lecture 17
Pushdown Automata
May 14 Lecture 18
Pushdown Automata
May 16 Lecture 19
CFG and PDAs
Homework 5 due
Reading: 2.3

May 19 Lecture 20
CFG and PDAs
May 21 Lecture 21
Closure Properties of CFLs
May 23 Lecture 22
Pumping lemma for CFL

Reading: 3.1 and 3.2

May 26 Holiday! No Class May 28 Lecture 23
Homework 6 due
May 30 Lecture 24
Turing Machines

Reading: 4.1 and 4.2

June 2 Lecture 25
June 4 Lecture 26
The Halting Problem
June 6 Final Review

Homework 7 due

June 9 Final Exam
2:30-4:20pm in EE 045

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to dabacon]