Office hours after class or by appointment or email.
Notes: Stephen A. Cook, Computability. (Handouts).
Here's the first installment of Professor Stephen Cook's course notes that we will be using.
Here's the second installment of Steve Cook's course notes that we will be using.
Book: Michael Sipser, Introduction to the Theory of Computation, (second or third edition) PWS Publishing Company, 2006.
We will start with Cook's computability notes. These will be followed by Sipser Chapters 4, 5.3 and 7, and familiarity with material in Sipser Chapter 3 and earlier chapters will be needed.Lists of Errata for the Sipser book can be found 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 (i.e. constructions and proofs.) 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 complete the York University Academic Honesty Tutorial and attend and participate in the twice-weekly classes, read assigned material from the text in advance of corresponding lectures and prepare individual, correct, well-written, neat answers for weekly homework exercises.The weekly homework component counts for 30% of the final grade. There will also 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 are currently scheduled to held in class on October 12, November 9 and December 5. I will provide notice in class of any changes.
Please note that there is no 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 or after class
well in advance.
Students must avoid all forms of academic dishonesty including plagiarism and must fully cite all resources used and all help received in preparing solutions to exercises and assignments. It is allowed to verbally discuss homework problems in general terms only (not detailed solutions) with another student (not a group), but each student must undertand and prepare their writeup of the solution entirely on their own and must not not share it (or drafts of it) with others. Acknowledge all ideas obtained from others. Do not copy solutions found on the internet. Searching the internet to use someone else's solution to a problem is plagiarism, unless the student's submission explicitly and precisely explains the use of, and cites the source for, each of the ideas used. Plagiarism is unlikely to help a student pass the course, and it could result in the student losing their degree. Please also read over the department, faculty and University policies concerning academic honesty. The consequences of academic dishonesty are generally severe in fourth year courses. Decisions about violations and the penalites are made by the Associate Dean and/or the responsible Lassonde Faculty committee.
Please read the material to be covered in each class in advance of the lecture. The readings will be specified in class.