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:, 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:, MCS 136


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.