image University of Washington Computer Science & Engineering
  CSE 322Wi '10:  Introduction to Formal Models in Computer Science
  CSE Home   About Us    Search    Contact Info 

 Schedule & Reading
 Midterm Review
 Final Review
Course Email
 Class List Archive
 HW #1
 HW #2
 HW #3
 HW #4
 HW #5
 HW #6
 HW #7
 HW #8
      HW #8 C/Java Starter Code
Lecture Notes
 Lecture 1, 1/4
 Lecture 2, 1/6
 Lecture 3, 1/8
 Lecture 4, 1/11
 Lecture 5, 1/13
 Lecture 6, 1/15
 Lecture 7, 1/18
 Lecture 8, 1/20
      NFA to DFA Notes
 Lecture 9, 1/22
 Lecture 10, 1/25
 Lecture 11, 1/27
 Lecture 12, 1/29
 Lecture 13, 2/1
 Lecture 14, 2/3
 Lecture 15, 2/5
 Lecture 16, 2/8
 Lecture 17, 2/10
 Lecture 18, 2/12
 Lecture 19, 2/15
 Lecture 20, 2/17
 Lecture 21, 2/19
 Lecture 22, 2/22
 Lecture 23, 2/24
 Lecture 24, 2/26
      CFG to PDA Notes
 Lecture 25, 3/1
 Lecture 26, 3/3
 Lecture 27, 3/5
 Lecture 28, 3/8
 Lecture 29, 3/10
 Lecture 30, 3/12

Lecture:  MGH 241 (schematic) MWF 1:30- 2:20 
Office Hours Location Phone
Instructor:  Larry Ruzzo, ruzzo at cs  M 2:30- 3:20  CSE 554  543-6298
TAs:  Punyashloka Biswal, punya at cs  Th 12:30- 2:20  CSE 218 
  Johnathan Lyon, jgl at cs  W 12:30- 1:20  CSE 220 
  Alex Piet, alexpiet at cs  Tu 1:30- 2:20  CSE 218 

Course Email: Use this list to ask and/or answer questions about homework, lectures, etc. The instructor is subscribed to this list. All messages are automatically archived.  Questions not of general interest may be directed to the instructor and/or TAs collectively (via the "course staff" link at left) or separately (via email addresses above). You can (probably should) change your subscription options.

Catalog Description: Finite automata and regular expressions; context-free grammars and pushdown automata; nondeterminism; Turing machines and the halting problem. Emphasis on understanding models and their applications and on rigorous use of basic techniques of analysis. Induction proofs, simulation, diagonalization, and reduction arguments.

Prerequisite: CSE 321

Credits: 3

Learning Objectives: The main goal of the course is to give students an ability to develop and rigorously reason about abstract formal models of computational devices, and an appreciation for the powers and limitations of such formalisms. An important secondary goal is to teach a body of facts about and techniques for studying ``classical'' models, such as finite automata and context-free grammars, having important applications in a variety of other areas of computer science, e.g., compilers and program specification.

Grading: Homework, Midterm, Final. Homework may include some programing. Overall weights: HW 55%, midterm 15%, final 30%, roughly.

Late Policy: Unless otherwise announced, papers and/or electronic turnins are due at the start of class on the due date. 10% off for up to one day late (business day, e.g., Monday for Friday due dates); additional 20% per day thereafter.

Extra Credit: Assignments may include "extra credit" sections. These will enrich your understanding of the material, but at a low points per hour ratio. Do them for the glory, not the points, and don't start extra credit until the basics are complete.

Collaboration: Homeworks are all individual, not group, exercises. Discussing them with others is fine, even encouraged, but you must produce your own homework solutions. Follow the "Gilligan's Island Rule": if you discuss the assignment with someone else, don't keep any notes (paper or electronic) from the discussion, then go watch 30+ minutes of TV (Gilligan's Island reruns especially recommended) before you continue work on the homework by yourself. You may not look at other people's written solutions to these problems, not in your friends' notes, not in the dorm files, not on the internet, ever. If in any doubt about whether your activities cross allowable boundaries, tell us before, not after, you turn in your assignment. See also the UW CSE Academic Misconduct Policy, and the links there.

Textbook: Michael Sipser, Intro. to the Theory of Computation, 2nd ed., Thompson Course Technology, 2005. Errata. (Available from U Book Store, Amazon, etc.)

Portions of the CSE 322 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 322 Web: © 1993-2010, Department of Computer Science and Engineering, University of Washington.

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