Theory of Computation

CSCI 361 / Math 361

Spring 2021

Catalog Description

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.

Meetings

Instructor

Aaron Williams

Office: TBL 309A

Phone: (413) 597-2774

Materials and Syllabus

Materials for the course are hosted on Google Classroom and are available only to students enrolled in the class.

Please contact the instructor for a copy of the syllabus.