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: