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.
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 |