CSE 322, Autumn 1998: Course Information

Instructor

Richard Ladner
311 Sieg Hall
206 543-9347
ladner@cs.washington.edu

Teaching Assistant

Yongshao Ruan
ruan@cs.washington.edu

Text

Elements of the Theory of Computation
Lewis and Papadimitriou
Prentice-Hall

Course 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.

Goals of the Course

Course Work