CPSC 046. Theory of Computation
(Cross-listed as MATH 046 )
This study of various models of computation leads to a characterization of the kinds of problems that can and cannot be solved by a computer. Solvable problems will be classified with respect to their degree of difficulty. Topics to be covered include formal languages and finite state devices; Turing machines; and other models of computation, computability, and complexity.
Group 1 course.
Prerequisite: CPSC 035 required. Mathematics background at the level of Linear Algebra or higher is required (may be taken concurrently).
Natural science and engineering.
Lab work required.
Spring 2018. Danner.
Catalog chapter: Computer Science
Department website: http://www.cs.swarthmore.edu/
Check the Fall 2017 Schedule of Courses