Course Overview

Prerequisites

• CS 2510 Fundamentals of Computer Science 2

• CS 2800 Logic of Computation

As important, perhaps, is the material from CS 1800, Discrete Structures, which itself is a prerequisite for CS2800.

To summarize, the course assumes the understanding of the program design, discrete structures, the foundations of symbolic logic, and mathematical maturity.

Course objectives

The goal is to understand the fundamentals of the theory of computation: the formal models of computation, the relationships between the different models of computation, the complexity of computation, and the limits of computability.

Text

Required: Introduction to the Theory of Computation, Third Edition, by Michael Sipser.

Errata for this text are available on-line. If you are concerned that something in the text might be a typo, please check the errata available here: Errata for Introduction to the Theory of Computation, Third Edition, by Michael Sipser.

Advice

Professor Viola wrote the words of advice for students in this class. Its title Thinking like a pro summarizes the contents: to really understand and learn the material in this course you need to think carefully about the precise definitions as well as understand their meaning to grasp their significance.