CAS 705: Computability and Complexity
Fall 2004
- 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
We will supplement it with the more advanced (not required, but
recommended)
Gems of Theoretical Computer Science, by U. Schöning and R.
Pruim
- Check this web page regularly for announcements. Some documents
will be available in PostScript; if you need a PostScript previewer,
go to Ghostview Software.
-
Last year's (2003) cas705 web site.
This course was also taught in 2002 as
cas776 -- Fall 2002.
- Please Read:
McMaster Academic Integrity Statement.
Announcements:
- Dec 20: The final exam has been posted below.
- Dec 18: Click here for a solution to
exercise 10.11 in Sipser (this is Liuxing Kan's problem). I included
some background material in the Chernoff bound.
- Dec 17: Click here for a solution to
exercise 10.14 in Sipser (this is Sabri Khair Eddin's problem; we did
one direction in today's class, but here are included both
directions).
- Dec 17: Click here for a solution to
exercise 10.16 in Sipser (this is Wang Shu's problem, were it turns
out that his solutions given in class is complete, and it was the
statement of the problem in the textbook that was incomplete: the a
for which the test fails has to be such that gcd(a,p)=1).
- Dec 1: I reserved room 222 for Friday Dec 17, 10:30--12:30, for
the final problem session. (Don't bring a coffee, as there is going
to be a treat of coffee and donuts!)
- Nov 26: Test 3 with solutions has been posted below.
- Nov 23: The final exam will take place on
December 20th, in ITB-222, from 10:30 until 1:30 (3 hours
exam).
- Nov 17: A big batch of slides (pages 48--81) has been posted
below. We will have a problem session on Friday, as stated below
(first Nov 12 announcement). Next week, we shall have our last test,
on Friday Nov 26. Test 3 will comprise chapters 7,8,9, and all the
related problems. The material on circuits presented in class today
is not part of the test.
- Nov 12: Update on Problem Sessions: On Tuesday (Nov 16), Ivan
will do question 2 from the "Additional Exercises" problem set, Inene
will do question 1, Sabina 7.12, Wang Shu 7.17, Ning will do 7.23, and
Khair Eddin will do question 3. On Friday (Nov 19) we will have
another problem session, where problems 8.9,10,12,13,16,18,19,20 will
be attempted.
- Nov 12:
Undirected ST-Connectivity in Log-Space
- Oct 22: To catch up with the problems, we will have another
problem session on Tuesday (Oct 26), where: Inene will finish 5.13,
Liu Ning will do 6.18, Tim 6.15, Sabina 6.19, and Liuxing 6.20.
- Oct 21: Additional exercises for Boolean expressions have been
posted below; you are not responsible for them for Test 2.
- Oct 21: Test 2 will take place as
scheduled on Friday October 29th, during the usual lecture time (in
the usual room, ITB/222). The test will include the following
chapters in Sipser: 4,5,6,7. (Note that in chapter 6 you are only
responsible for sections 6.3 & 6.4.) We will finish chapter 7 on
Tuesday and Wednesday, and we should have time on Wednesday to have a
mini problem session to help you with the problems in chapter 7.
- Oct 19: The latest slides have been posted below. Our next
problem session will be this Friday (Oct 22). The presenters will be:
Ivan (Q5.22), Wang Shu (Q5.17), Inene (Q5.13). Questions 3.17 is
still up for grabs; a neat solution would be appreciated.
- Oct 13: Problem Set 6 has been posted below.
- Oct 12: Slides 23-40 have been posted below, as well as problem
set 5 (i.e., all the exercises in Chapter 5).
- Oct 12: On Friday (next problem session) Khair Eddin Sabri will
present 1.42.
- Oct 8: Hints for exercises 3.17 and 4.13. For 4.13, realize
the following: the intersection of a regular language with a CFL is a
CFL, which has a particular grammar G, and therefore, by the Pumping
Lemma for CFLs, there is a p such that every string of at least p 1s
can be pumped at will. Using this, compute a number n such that if all
strings of 1s of length at most n are in the language, then all the
strings of 1s are in the language. The trick is to find n. For 3.17,
as was discussed in class, first show that every TM which works by
processing the input left to right without backtracking, and accepting
once the input has been read, is in fact a DFA (this is the easy
part). The second part (the hard part) is to show that the TM
described in 3.17 can be converted into such a TM--the main idea is
that a TM like the one in 3.17 cannot backtrack "meaningfully" for
more than a constant number of squares, as it cannot remember where it
left of. Formalize this. Sabina Horton has "volunteered" to do 4.13,
and Liuxing Kan has "volunteered" to do 3.17, but of course every one
should think about these two problems.
- Oct 2: Test 1 with solutions has been posted below.
- Sep 27: My office hours are on Tuesdays, 10:30-11:20 (in my
office, ITB/214), but you can also see me by making an appointment for
another time, or just by dropping by my office.
- Sep 27: Test 1 will take place on Friday (Oct 1), during the
usual lecture time (12:30-1:20) in the usual lecture room (ITB/222).
The test will cover chapters 1,2,3 in Sipser. To prepare for the
test, make sure that you do problem sets 1,2,3.
- Sep 27: Problem Set 3 has been posted below.
- Sep 27: On Tuesday (Sep 28) we will cover chapter 3 in Sipser.
On Wednesday (Sep 29) we will have another problem session, in
preparation for Test 1.
- Sep 20: We will have our first problem session on Friday Sep
24. We will cover the problems in chapters 1 and 2 of the textbook
(Sipser). To make good use of the problem session, you should have
most of the problems done, and have made serious attempts at the more
difficult ones. Remember that doing these problems is essential for
the understing of the course material, and for doing well on the
tests. Remember also that you do not hand in the problems. You are
encouraged to talk to each other about the more challenging problems.
- Sep 20: The three tests will take place on the following dates:
- Test 1: Oct 1
- Test 2: Oct 29
- Test 3: Nov 26
All tests are on Fridays; they will cover the material until, and
including, the previous Wednesday lecture. The tests will be written
in the usual classroom, and they will be 50min long (12:30-1:20 -- the
usual lecture time).
- Sep 7: First meeting will be on Friday, Sep 10, in
ITB/222
- Sep 1: The information sheet has been posted above. It will be
handed out during the first day of class (Friday, Sep 10, 12:30--1:20,
in ITB/222).
Tests, slides, and suggested exercises: