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.
Office hours after class or by appointment or email.
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.
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.
Please read the material to be covered in each class in advance of the lecture. The readings will be specified in class.