CSCI 361 - Theory of Computation

Institution:

Williams College

Subject:

Computer Science

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.

Credits:

3.00

Credit Hours:

Prerequisites:

Computer Science 256 or both a 300-level Mathematics course and permission of instructor

Corequisites:

Exclusions:

Level:

Instructional Type:

Lecture

Notes:

Additional Information:

Historical Version(s):

Institution Website:

www.williams.edu

Phone Number:

(413) 597-3131

Regional Accreditation:

New England Association of Schools and Colleges

Calendar System:

Four-one-four plan

The Course Profile information is provided and updated by third parties including the respective institutions. While the institutions are able to update their information at any time, the information is not independently validated, and no party associated with this website can accept responsibility for its accuracy.