Welcome to the home page for the Computer Science Department's undergraduate 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 Monday and Wednesday from 2:30 until 3:45 in CGS 511..
CS 332 is taught by Steve Homer (homer@bu.edu) Office : Room 1007, New Building
Office hours: Monday 11:00-12:00, Thursday 12:00-1:00 in Room 1007
The Teaching Fellow this semester is Nathan Dang
Office Hours: for Nathan are Tuesdays: 5:00 - 6:00 pm @ CDS 614 and Thursdays: 5:00 - 6:00 pm @ CDS 801
Temporary Zoom office hoursthis week: meeting ID: 591 199 8238, Passcode: hFamZ8
Discussion Sections All students should attend one of the three discussion section given on by our TF. These are:
Tuesday, 9:30am - 10:20am in PSY 35
Tuesday, 11:15am - 12:05pm in PSY 35
Tuesday, 12:30pm - 1:20pm in CDS 364
Gradescope and Piazza
We will be using both Piazza and Gradescope as part of this class. You should be able to sign up for Piazza and Gradescope on your own using the information below.
The course has a Gradescope Code which is: ZZ5D52
and a Piazza url which is : piazza.com/bu/spring2023/cs332
Course News
You can use this News file to keep track of some important dates for CS 332 during the semster.
Here is the most recent CS 332 course
news.
Current homework:
Past homeowrk: HW 0, HW 1, HW 2, HW 3, HW 4. HW 5
Some extra reading:
You can read Alan Turing's 1937 paper where Turing machines were first defined here.
Some Notes on Undecidability. You will find definitions and a few key results concerning undecidability here.
Here is an overview of course policy on homework.
The following list of pointers provides access to information concerning a recent version of the course and about the computer science department.