CS 381 - Introduction to Theory of Computing, Summer 2004

Welcome to the CS 381, Summer 2004 Website.

If you are not able to find the information you are looking for here, please let Lucja know. (See under "Course Info" for contact details).

Please make sure to check the Announcements section regularly (at least once a day) for important updates.

About CS 381

CS 381 is an introduction to the modern theory of computing. The course has three natural sections, and a rough overview of each section is given below (note that these are not intended as complete and exclusive lists of the topics we will cover).

Automata and regular languages: Deterministic and nondeterministic finite automata, regular languages, regular expressions and pattern matching, closure properties of regular languages, the limits of automata and the pumping lemma, automata minimization, decision problems for automata.

Context-free languages: Context-free grammars and normal forms, pushdown automata, the pumping lemma for context-free languages, closure properties of context-free languages, the practical use of context-free grammars in parsing.

Effective computability and Turing Machines: the Turing Machine, the Church-Turing thesis, r.e. and recursive languages, decidability and undecidability, the Halting Problem, reductions, Rice's theorem.

CS 381 is offered in the summer and fall semesters; in terms of material covered and workload, both offerings are equivalent.

In the fall semester, the department also offers CS 481, which is a somewhat deeper and faster-paced course covering the same topics as CS 381. If you have questions about CS 481 or other relevant courses, please do not hesitate to contact Lucja.