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:
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.