CAS 705: Computability and Complexity
Fall 2003

• Instructor: Michael Soltys, email: my last name at mcmaster.ca
• Course Information
• Course outline: The relationship between problems, algorithms, and languages. Computability: finite automata, rewriting systems, Turing machines (linear speedup, robustness, and the Universal Turing machine). Recursive functions and Cobham's Theorem. Determinism and non-determinism. Recursive and recursively enumerable languages. The Halting problem and the diagonalization technique. Church-Turing thesis, and Rice's theorem. Complexity: classes defined in terms of time, space, and circuits. Uniformity. The reachability method (Savitch's theorem, and the Immerman-Szelepscenyi theorem). The P versus NP problem (and Cook's Theorem), reductions and completeness. The Time and Space Hierarchy Theorems. Randomized and parallel computations. NP and co-NP, propositional proof systems, and Horn clauses. Kolmogorov complexity, and the Shannon principle.
• Textbook: Introduction to the Theory of Computation, By Michael Sipser
  
• Check this web page regularly for announcements. Some documents will be available in PostScript; if you need a PostScript previewer, go to Ghostview Software.
• This course was taught last year as cas776--Fall 2002. Keep in mind however, that it was given as a "group B" course, and this year it is given as a "group A" course, so there are differences in the approach (and a different textbook).
• Please Read: McMaster Academic Integrity Statement.

Announcements:

• Nov 28: The final exam has been posted below.
• Click here for the slides on Chapter 9 in Sipser.
• Nov 4: Solutions to Test 2 have been posted below.
• Nov 3: Click here for a solution to exercies 8.12 in the textbook.
• Oct 31: Click here for a solution to exercies 7.34 in the textbook.
• Oct 28: On Friday Oct 31 we will have a problem session for Test 2 (Chapters 7 and 8).
• Oct 17: Important Dates:
  • Test 2: Nov 4th, Tuesday, in ITB/222 (usual classroom).
  • Review: Nov 26th, Wednesday.
  • Final Exam: Nov 28th, Friday, 12:30--3:30 in ITB/222 (usual classroom).
• Oct 16: Problem Set 4 has been posted below.
• Sep 30: My official office hours are on Fridays at 10:30, but you can make an appointment for another time, or just drop by (ITB/214).
• Sep 30: Problem Set 3 has been posted below.
• Sep 30: The schedule of (some) presentations has been posted below.
• Sep 25: Test 1: Friday, Oct 10, during the usual lecture hour. The test will comprise Chapters 1--6.
• Sep 25: On Friday Oct 3, we will have a problem session instead of a lecture. Bring the problems that you are having difficulties with, and we will brain-storm them.
• Sep 25: Problem Set 2 has been posted below.
• Sep 24: Please select a presentation topic soon. You can drop by my office to discuss the list of topics in the "Gems" book at any time.
• Sep 16: Problem Set 1 has been posted below.

Tests and suggested exercises:

• Problem Set 1
• Problem Set 2
• Schedule of Presentations (revised Nov 11, 03)
• Problem Set 3: Chapter 6, exercises 2,3, and problems 5--7,13--17,20--22.
• Test 1 with solutions
• Problem Set 4
• Test 2 with solutions
• Final Exam