Course Descriptions

CS U390: Theory of Computation

View Course Charter

Introduces the theory behind computers and computing aimed at answering the question: “What are the capabilities and limitations of computers?” Covers automata theory, computability, and complexity. The automata theory portion includes finite automata, regular expressions, non-determinism, non-regular languages, context-free languages, pushdown automata, and non-context-free languages. The computability portion includes Turing machines, the Church-Turing Thesis, decidable languages, and the Halting Theorem. The complexity portion includes big-O and small-o notation, the classes P and NP, the P versus NP question, and NP-completeness.

Prerequisites: CSU213 and PHLU215 (Symbolic Logic).

Credit hours: 4 SH

Course offerings:
• Spring 2008
• Fall 2007
• Fall 2006
• Spring 2006
• Fall 2004
• Fall 2003