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.
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 (firstname.lastname@example.org). Office hours: Tuesday 3:30 - 4:30, Wednesday 1:30-2:30 in MCS 281.
The Teaching Fellow this semester is Jiayu Zhang, email@example.com.
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.
The following list of pointers provides access to information concerning a recent version of the course and about the computer science department.