 Class Meetings

 Lectures: Mon, Wed, Fri 1011, CAS 316

 Instructor: Peter Gacs

 Office Hours: Wed 45:30, Fri 45:30 or by appointment.

 Coordinates: gacs@bu.edu, MCS277, 6173532015

 Teaching Assistant: Yilei Chen

 Lab Hours: Mon 121, 12, 45, MCS B33

 Office Hours: Tue 910:30, Thu 23:30 in Yilei's office.

 Coordinates: chenyl@bu.edu, MCS 136

 Textbooks

 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, NPcompleteness;
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.