Welcome to the home page for the Computer Science
Department's **Theory of Computation** course CAS CS
332.

*CS 332* is the main undergraduate course in computability
theory and complexity theory within the undergraduate computer science curriculum. Topics
covered include Turing machines, universal computation, Church's thesis,
decidability, reductions, a variety of unsolvable problems, NP-completeness,
a variety of NP-complete problems, resource bounded complexity, and common complexity classes.

Course Information:

Please consult the syllabus for the details of topics covered this semester, grading details and other course information.

The class meets Tuesday and Thursday from 2:00 until 3:15 in SAR 102.

CS 332 is taught by Steve Homer (homer@bu.edu). Office hours: Tuesday 3:30 - 4:30, Wednesday 1:30-2:30 in MCS 281.

The Teaching Fellow this semester is Jiayu Zhang, jyz16@bu.edu.

Office Hours: Wed 11-12am, Thu 3:30-4:30pm in MCS 135A

All students should attend one of the three lab section given on Monday of each week by the Teaching Fellow. These are:

Monday, 11:15am - 12:05pm in MCS B19

Monday, 12:20pm - 1:10 pm in MCS B25

Monday, 1:25pm - 2:15pm in MCS B25

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

The midterm will be in class on Thursday March 7;

You can find a short practice midterm here.

Current homework: HW6.

Here are the previous homeworks:

- HW1
- HW2
- HW3
- HW4
- HW2
- HW3
- 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).

Here are some brief answers to some of the problems in the HW's

You can find the handout (from the book by John Savage) giving a reduction from the Halting problem to the empty tape acceptance problem here.

You can read Alan Turing's 1937 paper where Turing machines were first defined here.

Two quite accessible and not too formal YouTube lectures on the Church-Turing Thesis can be found here and here.

The following list of pointers provides access to information concerning a recent version of the course and about the computer science department.