Skip to main content

CS154

Introduction to the Theory of Computation

Computer Science ENGR - School of Engineering

Course Description

This course provides a mathematical introduction to the following questions: What is computation? Given a computational model, what problems can we hope to solve in principle with this model? Besides those solvable in principle, what problems can we hope to efficiently solve? In many cases we can give completely rigorous answers; in other cases, these questions have become major open problems in computer science and mathematics. By the end of this course, students will be able to classify computational problems in terms of their computational complexity (Is the problem regular? Not regular? Decidable? Recognizable? Neither? Solvable in P? NP-complete? PSPACE-complete?, etc.). Students will gain a deeper appreciation for some of the fundamental issues in computing that are independent of trends of technology, such as the Church-Turing Thesis and the P versus NP problem. Prerequisites: CS 103 or 103B.

Grading Basis

ROP - Letter or Credit/No Credit

Min

3

Max

4

Course Repeatable for Degree Credit?

No

Course Component

Lecture

Enrollment Optional?

No

Does this course satisfy the University Language Requirement?

No

Programs

CS154 is a completion requirement for: