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

Learn about and understand fundamental models of computation.
Strengthen ability to think abstractly.
Strengthen ability to mathematically prove facts.

Course Work

Weekly homework, due on Fridays (25%)
Midterm Exam, Friday, November 6th (25%)
Final Exam, Friday, December 11th, 8:30 - 10:20 am (50%)