**Theory of Computation (Q)**

Cross Listed as CSCI361

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.

**lecture**

*Class Format:***evaluation will be based on problem sets, a midterm examination, and a final examination**

*Requirements/Evaluation:*

*Additional Info:*

*Additional Info2:***CSCI 256 or both a 300-level MATH course and permission of instructor**

*Prerequisites:***current or expected Computer Science majors**

*Enrollment Preference:*

*Department Notes:*

*Material and Lab Fees:*

*Distribution Notes:***Division III,Quantitative and Formal Reasoning**

*Divisional Attributes:***COGS Interdepartmental Electives**

*Other Attributes:***40**

*Enrollment Limit:***40**

*Expected Enrollment:***1428**

*Class Number:*CLASSES | ATTR | INSTRUCTORS | TIMES | CLASS NUMBER |
---|---|---|---|---|

MATH 361 - 01 (F) LEC Theory of Computation (Q) | Brent A. Heeringa |
MWF 12:00 PM-12:50 PM Physics 205 | 1428 |