CSE 322: Introduction to Formal Models in Computer Science

Paul Beame, Winter 1999

MWF 2:30-3:20, Mueller 155

StaffNameEmailPhoneOffice Hours
Instructor: Paul Beame beame@cs 543-5114W 3:20-3:50, Th 11:00-11:50, F 3:20-3:50Sieg 416
TA: Matt Cary cary@cs616-1843T 4:30-5:20, Th 4:30-5:20Sieg 226a,b

Class E-mail Archive: (Last update: [an error occurred while processing this directive].)
(This is a log of all messages sent to the class e-mail list.)
To send mail to the whole class, mail to: cse322@cs.washington.edu
Instructions on how to subscribe to the cse322 mailing list can be found here.


Lewis & Papadimitriou Elements of the Theory of Computation: Second Edition, Prentice Hall, 1998.

This is the new edition that has the picture of Alan Turing on its cover. The old edition is not suitable. There is a list of typos available.


Conversion of PDA's to CFG's
Pumping Lemma for CFL's
Converting to Chomsky Normal Form
Cocke-Kasami-Younger Algorithm example


Homework is intended to be a major portion of the course. Assignments will be due weekly, usually on Friday. It is expected that homework solutions represent original work.

Assignment #1
Assignment #2
Assignment #3
Assignment #4
Assignment #5
Assignment #6
Assignment #7

Anonymous (or not) feedback form to tell us how things are going.


The course grade will be based on homework, a midterm, and a final exam. The approximate weighting of the three components is 40-50% Homework, 15-25% midterm and 30-40% final exam.


February 12 in class Topics for the midterm

Final Exam

Tuesday March 16, 2:30-4:20 in class Topics for the final
Sample final

Old Course Webs:

Autumn 1997 Winter 1998 Spring 1998 Autumn 1998

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: Copyright 1999, Department of Computer Science and Engineering, University of Washington.
Comments to:
(Last Update: 03/21/05 )