CSCI 361(F) Theory of Computation (Same as Mathematics 361) (Q)
This course introduces a formal framework for investigating both the computability and complexity of problems. We study several models of computation including finite automata, regular languages, context-free grammars, and Turing machines. These models provide a mathematical basis for the study of computability theory-the examination of what problems can be solved and what problems cannot be solved-and the study of complexity theory-the examination of how efficiently problems can be solved. Topics include the halting problem and the P versus NP problem.
Format: lecture. Evaluation will be based on problem sets, a midterm examination, and a final examination.
Prerequisites: Computer Science 256 or both a 300-level Mathematics course and permission of instructor. Enrollment limit: 30 (expected: 20).
Hour: HEERINGA