- Assignments
- Instructor
- Teaching Assistant
- Textbook (and errata)
- Background required
- Course description
- About the text
- Course outline
- Course work
- Due Dates (tentative)

Office hours: W 3:30-4:30 or by appointment

Please feel free to drop by with course questions or just to chat. You can often find me in at other times; email to make sure.

There is also a page for errata that you should read in order to update your copy of the text. In fact, you should also look at this errata, since it has quite a few errors which are not in the original.

You should have seen Turing machines and their variants as a model for studying computation. You should know the basics of undecidability, time complexity and NP-completeness. At Waterloo, CS 360 and CS 341 cover these topics quite adequately. See me if you feel unsure about your background.

We shall consider the basic resources of time and space (memory), as well as less-quantifiable resources such as nondeterminism, randomization, interaction and parallelism. For each, we shall identify ``complete'' problems that characterize the use of the resource or investigate why no such problems exist.

The various resources have close connections to one another, singly
and in combination. Along with showing the known connections, we
shall discuss why some relationships remain unknown. In particular,
we shall look at some recent approaches to the

Each chapter ends with a collection of ``Notes, References and Problems.'' Some of them merely amuse, but others point to additional insights and results. I shall take some of the lecture material from these sections.

*Basics and review*(1 week):- Turing machines: definitions and notation. Time and space complexity. Linear speedup. (Ch. 2.)
*Undecidability and Logic*(1 week)- UTM, halting, recursive, recursively enumerable, recursively separable. (Chs. 3 and 4)
*First and Second order logic*(1 week)- Godel's completeness theorem. (Ch. 5)
*Number theory and complexity*(1 week):- Godel's incompleteness theorem. (Ch. 6)
*Complexity classes and completeness*(1 1/2 weeks):- Equivalence and separation of classes. Reductions and completeness for general classes. (Chs. 7 and 8.)
*Nondeterminism*(2 weeks).- A variety of NP-complete problems. Complementary problems. (Chs. 9 and 10.)
*Randomization, interaction, and approximation*(2 weeks):- Randomization as a computational resource (Ch. 11). Its use in two-party computations (Ch. 12). Two-party computations and (non)approximability of NP-complete problems (Ch. 13).
*Parallel computation*(2 weeks):- Very fast parallel computation. Parallel models: PRAMs, circuits, and alternation. (Chs. 15 and 16.)
*Beyond NP: polynomial space*(1 week):- Relations of
polynomial space bounds to time, parallelism and interaction.
(Ch. 19.)

**Homework assignments:**

There will be four homework assignments, which I expect to be due in class on Fridays: January 28, February 15, March 8, and March 29. Sixty percent of the course grade will be based on these assigned problems.

You must do your own work on the assigned problems. You are permitted to
discuss *general aspects* of the assigned problems with other
students in the class, but you must create your own solution based on
your own understanding of the material. Normally, a discussion in
which one of the participants writes something down for the other
prevents doing one's own work. You are of course free to discuss the
problem with the instructor or the TA.

Along with the assigned problems, I will suggest some non-credit study problems. The problems will vary in difficulty from very easy to very hard; some may involve library readings. I intend that you will use these problems to practice the material and to deepen your understanding. You are free to use these non-credit problems as you see fit: solve them yourself, discuss them with friends, ask questions of me or the TA, etc.

**Exams:**

The final examination will be a take-home; you will choose a period of several days within the normal exam period in which to write it. The take-home exam will require understanding and interpretation which is deeper than the assignments. The take-home exam is 40% of the course grade.

**Students taking CS 664:**

Students taking this course as CS 664 will complete a written project which will be worth 20%. Assignments and the take-home final will be worth 40% each.

Friday, January 28 | Assignment 1 |

Friday, February 15 | Assignment 2 |

Friday, March 8 | Assignment 3 |

Friday, March 29 | Assignment 4 |

TBA | Final Exam |