Steam-powered Turing Machine University of Washington Computer Science & Engineering
 CSE 322 Autumn 2008
  CSE Home     CSE 322  About Us    Search    Contact Info 

Class Communications
 Anonymous Comment Form
 Class Mailing List
 Mailing List Archive
Homework
 Assignment 1
 Assignment 2
 Assignment 3
 Assignment 4
 Assignment 5
 Assignment 6
 Assignment 7
 Assignment 7 sols
Lecture Notes
 Introduction
 DFA Formal Defintion
 Regular Operations
 Nondeterministic Finite Automata
 NFA to DFA Construction
 Closure of Regular Operations
 Regular Expressions
 Regular Expressions and GNFAs
 Pumping Lemma for Regular Languages
 Myhill-Nerode Theorem
 Minimizing DFAs
 Sting Matching
 Intro to CFGs
 Chomsky normal form
 Pushdown Automata
 PDAs and CFGs
 Closure properties of CFLs
 Pumping Lemma for CFLs
 CKY algorithm (Beame)
 Turing Machines
 Decidability
Midterm/Final
 Midterm Topics
 Sample Midterm 1
 Sample Midterm 2
 Sample Midterm 2 Sols
 Final Topics
 Final Sample (Beame)
 Final Sample Sols
Handouts/Other Notes
 Seattle DFA
 Defining Delta Star (Beame)
 Myhill Nerode Theorem (Beame)
 Minimizing DFAs (Beame)
Administrative
 Standard Syllabus
 This Quarters Syllabus
 Homework/Collaboration Policy
   

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

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

Office Hours Location Phone
Instructor: Dave Bacon   dabacon at cs  
Monday 2:30-3:00
Wednesdays 11:00-12:00
Friday 12:00-1:00
or by appointment
CSE 460 221-6503
TAs: Alice Neels    neelsa at cs   CSE 216 Thursday 11:30-12:20
Aaron Miller   ajmiller at cs   CSE 216 Thursday, 1:30-2:20

Final Exam: The final exam is Monday, Dec. 8 from 2:30-4:20 p.m. in EEB 037. It is closed notes, no calculators needed. There will be a review session in class on Friday, Dec. 5. A list of topics and sample finals are located on the sidebar

Midterm: The midterm is Wednesday, October 29, in class. It is closed notes, no calculators needed. Midterm topics as well as sample midterms on located on the sidebar. There will be a review session Sunday, Oct 26 at 4:30pm in EEB 037.

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.

Calendar:


Week Monday Wednesday Friday
1
Reading:
0.1-0.4,1.1
Sep. 23 Lecture 1
Welcome and Introduction
Sep. 26 Lecture 2
Finite Automata
Formal definition
2
Reading: 1.2

Sep. 29 Lecture 3
Finite Automata
Regular operations
Oct. 1 Lecture 4
Nondeterministic Finite Automata
Oct. 3 Lecture 5
Equivalence Between NFA and DFA
3
Reading: 1.3

Oct. 6 Lecture 6
Closure Properties of FA
Homework 1 due
Oct. 8 Lecture 7
Regular expressions
Oct. 10 Lecture 8
Regular expressions and DFAs
Homework 2 due
4
Reading: 1.4

Oct. 13 Lecture 9
Regular expressions and DFAs
Oct. 15 Lecture 10
Pumping Lemma for DFAs
Oct. 17 Lecture 11
Pumping Lemma for DFAs
Homework 3 due
5
Reading: 2.1

Oct. 20 Lecture 13
Myhill-Nerode
Oct. 22 Lecture 12
Myhill–Nerode Theorem
Oct. 24 Lecture 14
DFA Minimization/Pattern Matching
Homework 4 due
6
Reading: 2.1

Oct. 27 No Lecture Oct. 29 Midterm In Class!
Oct. 31 (Boo!) Lecture 15
Pattern Matching

7
Reading: 2.2

Nov. 3 Introduction to Context Free Languages
Nov. 5 Lecture 17
Ambiguity in CFGs
Nov. 7 Lecture 18
Chomsky Normal Form
8
Reading: 2.3

Nov. 10 Lecture 19
Pushdown Automata
Homework 5 due
Nov. 12 Lecture 20
Pushdown Automata
Nov. 14 Lecture 21
Closure Properties of CFLs
9
Reading: 3.1 and 3.2

Nov. 17 Lecture 22
CFG and PDAs
Nov. 19 Lecture 23
Pumping lemma for CFLs

Nov. 21 Lecture 24
Pumping lemma for CFLs
Homework 6 due
10
Reading: 4.1 and 4.2

Nov. 24 Lecture 25
Cocke-Younger-Kasam
Nov. 26 Lecture 26
Turing Machines
Nov. 28 Thanksgiving Holiday
10
Reading: 4.2

Dec. 1 Lecture 27
Decidability
Dec. 3 Lecture 28
The Halting Problem
Dec. 5 Final Review
Homework 7 due
11


Dec. 8 Final Exam
2:30-4:20pm in EE 037






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