Theory of Computation

CSCI 361 / Math 361

Fall 2019

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

Lectures: MWF 11:00 am - 11:50 am

Room: TCL 202

Instructor

Aaron Williams

Office: TBL 309A

Phone: (413) 597-2774

Teaching Assistants

William Burford

Jonathan Carrasco-Noriega

Peter Christie

Jack Murphy

Daniel Yu

Materials and Syllabus

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

The full syllabus for the course is available here.