To determine if a course is remote, hybrid, or in-person use the catalog search tool to narrow results. Otherwise, when browsing courses, the section indicates teaching mode:
R = Remote
H = Hybrid
0 = In-person
Teaching modes (remote, hybrid, in-person) are subject to change at any point. Please pay close attention when registering. Depending on the timing of a teaching mode change, faculty also may be in contact with students.
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: lecture/conference; Lecture content will be through asynchronously viewed video modules. Two scheduled course sections will be used for synchronous conference meetings. One section (MR) will be in-person and the other section (TR) will be remote. Students should sign up for lecture and one conference.
Grading: yes pass/fail option,
no fifth course option
CSCI 256 or both a 300-level MATH course and permission of instructor
current or expected Computer Science majors
This course is cross-listed and the prefixes carry the following divisional credit:
This course include regular and substantial problem sets in which quantitative/formal reasoning skills are practiced and evaluated.
COGS Interdepartmental Electives