CSCI 387 - Computability and Complexity

Introduction to models of computation including finite automata, formal languages, and Turing machines, culminating in universality and undecidability. An introduction to resource-bounded models of computation and algorithmic complexity classes, including NP and PSPACE, and the notions of relative hardness and completeness.

Unit(s): 1
Group Distribution Requirement(s): Distribution Group III
Prerequisite(s): CSCI 121 or equivalent and MATH 112 and MATH 113
Instructional Method: Lecture-conference
Grading Mode: Letter grading (A-F)
Cross-listing(s): MATH 387
Group Distribution Learning Outcome(s):

Use and evaluate quantitative data or modeling, or use logical/mathematical reasoning to evaluate, test or prove statements.
Given a problem or question, formulate a hypothesis or conjecture, design an experiment, and collect data or use mathematical reasoning to test or validate it.