Class Meetings

Lectures: Mon, Wed, Fri 10-11, CAS 316

Instructor: Peter Gacs

Office Hours: Wed 4-5:30, Fri 4-5:30 or by appointment.

Coordinates: gacs@bu.edu, MCS-277, 617-353-2015

Teaching Assistant: Yilei Chen

Lab Hours: Mon 12-1, 1-2, 4-5, MCS B33

Office Hours: Tue 9-10:30, Thu 2-3:30 in Yilei's office.

Coordinates: chenyl@bu.edu, MCS 136

Textbooks

• (required) Sipser: Introduction to the Theory of Computation, 3rd edition, Cengage, ISBN 9781133187790
• (recommended)
  • Lovasz: Computation Complexity (translation by Gacs) (for a more algorithmic perspective of some of the material)
  • Lewis-Papadimitriou: Elements of the Theory of Computation, second edition, Prentice-Hall 1998 (for more exercises on the elementary concepts)
  • Leonid A. Levin: Fundamentals of Computing (for a highly optimized exposition of some of the material)

General description

The basic concepts of the theory of computation are studied. Topics include: Turing machines and other models of computation; Church's thesis; nondeterminism; universal algorithms, undecidability and intractability; time and space complexity; reductions of computational problems, NP-completeness; randomized algorithms. The student is expected to get a broader perspective about what is possible and what is impossible to do with the help of computers. We will learn various methods of acquiring this kind of knowledge.

Prerequisites

CS330.