Computability and Complexity

COSC 4111.03 Winter 2010


Course news will be posted here as needed. Please refresh and check frequently, especially right before assignments and tests.

February 6

Test 1 is scheduled this Thursday, February 11, in class 4-5:30.

Aids allowed: one (two-sided) sheet of notes.

January 12, 2010

Tests will be in class on February 11, March 11, and April 1.

Here's the first installment of Cook's notes that we will be using.

Here's the second installment of Cook's notes that we will be using.

Old news


Prof. Patrick Dymond
CSB 3052C
email: my last name

Office hours after class or by appointment or email.


Tuesday, Thursday, 4:00 - 5:30 p.m., CC 208 (Calumet College)
Late enrollment in the course is not advisable unless the student has been attending classes since the the first lecture, and has kept up with readings and assignments. Attendance will be taken to provide documentation for any such cases.


Notes: Stephen A. Cook, Computability. (Handouts).

Michael Sipser, Introduction to the Theory of Computation, (second edition) PWS Publishing Company, 2006.

We will start with Cook's computability notes. These will be followed by Sipser Chapters 4-7, and familiarity with material in Chapter 3 and other chapters will be needed.

Lists of Errata for the book can be found here.

Some suggested problems and exercises from the book will be listed here.

Here are some other useful references


This is a course in the mathematical theory of computation. It is intended to give a detailed understanding of the basic concepts of abstract machines, information flow, computability, and complexity. The emphasis will be on appreciating the significance of these ideas and the formal techniques used to establish their properties. Topics chosen for study include: models of computation, primitive recursive and partial recursive functions, the Church-Turing thesis, limits to computation (undecidablility), reducibility, Rice's theorem and the recursion theorem, Godel's theorem, productive and creative sets, and the intrinsic difficulty of computational problems (especially NP-completeness).


CSE 2001, CSE 3101, general fourth-year CSE prerequisites.

Course Requirements:

Students attend and participate in the twice-weekly classes, read assigned material from the text in advance of corresponding lectures and prepare individual, well-written answers for assignments and/or exercises prior to class, and present them in class or hand them in as required. There will be two full hand-in assignments, and several hand-in single problems. This component counts for 30% of the final grade. There will be three eighty minute midterm tests, the first two each counting for 25% and the last one counting for 20% of the final grade. The tests will be held in class on February 11, MArch 11 and April 1 I will provide notice in class and here of any changes.

Please note that there is no special provision for making up late exercises, assignments or missed classes or tests. Without sufficient medical documentation that you were both unable to perform the required tasks and unable to contact the instructor throughout the period prior to the scheduled date, missed material is to be assigned a score of zero. If problems arise in meeting a deadline, please contact the instructor by email well in advance.
You should avoid plagiarism and fully cite all resources used in preparing solutions to exercises and assignments. You are allowed to verbally discuss problems with others, but prepare your writeup of the solution on your own and do not share it with others. Please also read over the department and faculty policies concerning this.

Course Schedule and Readings:

Please read the material to be covered in each class in advance of the lecture. The readings will be specified in class.


A list of related reference books is available.