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 Homework  Assignment #1  Assignment #2  Assignment #3  Assignment #4  Assignment #5  Assignment #6  Assignment #7  Extra credit Lecture Notes  Introduction  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  Decidability Midterm/Final  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) Administrative  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 Calendar: Week Monday Wednesday Friday 1 Reading: 0.1-0.4,1.1 Mar. 31 Lecture 1 Welcome and Introduction Apr. 2 Lecture 2 Finite Automata Formal definition Apr. 4 Lecture 3 Finite Automata Regular operations 2 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 3 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 4 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 5 Reading: 2.1 Apr. 28 Lecture 12 Myhill-Nerode Apr. 30 Lecture 13 DFA Minimization/Introduction to Context Free Languages May 2 Lecture 14 Context Free Languages 6 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! 7 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 8 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 9 Reading: 3.1 and 3.2 May 26 Holiday! No Class May 28 Lecture 23 Cocke-Younger-Kasam Homework 6 due May 30 Lecture 24 Turing Machines 10 Reading: 4.1 and 4.2 June 2 Lecture 25 Decidability June 4 Lecture 26 The Halting Problem June 6 Final Review Homework 7 due 11 June 9 Final Exam 2:30-4:20pm in EE 045

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