MATH 361
Theory of Computation Fall 2018 Division III; Quantative/Formal Reasoning; Cross-listed as CSCI361 / MATH361

Catalog Search

Class Details

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.
The Class: Type: lecture
Limit: 34
Expected: 34
Class#: 1605
Requirements/Evaluation: evaluation will be based on problem sets, a midterm examination, and a final examination
Extra Info: may not be taken on a pass/fail basis; not available for the fifth course option
Prerequisites: CSCI 256 or both a 300-level MATH course and permission of instructor
Enrollment Preference: current or expected Computer Science majors
Distributions: Division III; Quantative/Formal Reasoning;
Attributes: COGS Interdepartmental Electives;

Class Grid

Course Catalog Search

TERM




SUBJECT
SUBJECT ATTRIBUTES
DIVISION



DISTRIBUTION



ENROLLMENT LIMIT
COURSE TYPE
Start Time
End Time
Day(s)