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

This is the starting point for online course information and documentation.

The class meets Monday and Wednesday from 2:30 until 3:45 in CAS 211.

CS 332 is taught by Steve Homer (homer@bu.edu). Office hours: Monday 4-5, Wednesday 4-5 in MCS 281.

Please consult the syllabus for the details of the course, grading and other course information.

The Teaching Fellow this semester is Kinan Dak Al Bab.

Office Hours: Tuesday 2:00- 3:30 and Wednesday 12:00 - 1:30 in the lab (room 302) in 730 Comm.

The two sections for our class are

- Monday at 12:20 in MCS B19 and
- Monday at 1:25 in KCB 103

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

Here is the current homework: HW 6.

Here are the previous homeworks:

- HW0
- HW0.1
- HW 1
- HW 2
- HW 3
- HW 4
- HW 5
- midterm .
- 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 the

Here are some brief answers to some of the problems in (many written by Kinan Bab)

Posted here are slides containing some background material. They were written by Prof. Emanuele Viola.

Here you can find Alan Turing's 1937 paper where Turing machines were first defined.

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

Class notes on computable reductions be be found here. ----------------------------------------------

Here is an overview of course policy on homework,

*CS 332* is the main undergraduate course in computability
theory and complexity within the computer science curriculum. Students
will learn about Turing machines, universal computation, Church's thesis,
decidability, reductions, a variety of unsolvable problems, resource
bounded complexity, and common complexity classes.

The following list of pointers provides access to information concerning the course.