Welcome to the home page for the Computer Science
Department's **Theory of Computation** course CAS CS
332. This is the starting point for online course information and
documentation.

The class is taught by Steve Homer (homer@bu.edu) whose office hours are Monday 11-12, Wednesday 2:00-3:00 and Thursday 2:00-3:00 in MCS 281.

Please consult the syllabus for the details of the course, grading and other course information.

The Teaching Fellows this semester are Maryam Ghasemi (ghasemi@bu.edu) Office Hours: Tueseday 3:30-5:30 and Thursday 4-5 in PSY 223 and Oxana Poburinnaya (oxanapob@bu.edu) Office Hours: Mon 4:30-6:00, Wed 11-12:30 in PSY 225

The three sections for our class are

- Monday at 12:00
- Monday at 1:00 and
- Monday at 4:00. All section in room B33 of the MCS building.

A copy of the midterm with (brief) answers given is here.

Here is a short but very complete example of a computable reduction.

Here is the most recent *CS 332* course
news.

Here is the current homework: HW

Here are the previous homeworks:

Here are some brief answers to some of the problems in

Here you can find Alan Turing's 1937 paper where Turing machines were first defined.

Here is an overview of course policy.

*CS 332* is the main undergraduate course in computability
theory and complexity within the computer science curriculum. Students
will learn about Turing machines, universal computation, Church's thesis,
decidability, reductions, a variety of unsolvable problems, resource
bounded complexity, and common complexity classes.

The following list of pointers provides access to information concerning the course.

- Course Information
- Computer Science Department Information
- Help and Other Places in Cyberspace (courtesy of A. Kfoury)
- A Historical Note on Algorithms
- Steve Seiden's Cheat Sheet(ten pages of commonly used formulas in computer science).