CSCI 361: Theory of Computation [MATH 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: Lectures. Evaluation will be based on problem sets, a midterm examination, and a final examination.

Prerequisites: CSCI 256 or both a 300-level mathematics course and permission of the instructor.

Course webpage: http://www.cs.williams.edu/~tom/courses/361

Taught by: Heeringa, Murtagh

Scheduled offerings:
Fall 2016
361-01 (LEC) MWF 12:00-12:50

Past offerings:
Fall 2015
361-01 (LEC) MWF 12:00-12:50

Fall 2014
361-01 (LEC) MWF 12:00-12:50

Fall 2013
361-01 (LEC) MWF 12:00-12:50