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, resource bounded complexity, and common complexity classes.

Course Information:

Please consult the syllabus for the details of the what the course covers this semester, grading details and other course information which will not change during the semester.

The class meets Tuesday and Thursday from 2:00 until 3:15 in CAS B18.

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

The Teaching Fellow this semester is Hannah Flynn (hmflynn@bu.edu).

Office Hours: Wednesday 3-4 and Thursday 12:30-1:30 in the CS Dept Lab, room 302 of 730 Comm. Ave.

Here is the most recent CS 332 course news.

Current homework: HW6 .

Here are the previous homeworks:

  1. HW1
  2. HW2
  3. HW3
  4. HW4
  5. HW5 <\li>

Here are some brief answers to some of the problems in the midterm and the HW's (many written by Hannah Flynn)

  1. midterm w/answers
  2. HW1
  3. HW2
  4. HW3
  5. HW4

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

Two quite accessible and not too formal YouTube lecture 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.