 |
Course
Description
This
course is an introduction to the mathematical foundations of the theory
of computation. We will study automata theory, formal languages, the
theory of computability and undecidability, and computational
complexity. This material is central to many branches of computer
science; it underlies the basic theory of compiler design, the
efficiency of algorithms, and the limitations of computing.
Course Materials
- Syllabus
- Tentative Schedule (with lecture notes)
- Textbook: Introduction to the Theory of Computation,
Second Edition, Sipser,
ISBN-10: 0534950973 ISBN-13: 9780534950972 -
Non-required: Compilers Principles, Techniques, and Tools by Alfred V. Aho Addison-Wesley (The red dragon book! ISBN: 0-201-10088-6)
- JFLAP
- Science Daily: Computers and Math news
- CS Lab FAQ