CS254Spring 2003Sec1Home Page/Syllabus

Theory of Computation

This course will cover the basics of computability and complexity theory. We will begin by studying Turing machines and other computation models and analyze various simulations techniques between these models. The simulation algorithms we develop actually often turn out to be useful when porting code from one programming language to another. We then consider the halting problem and the theory of undecidibility. Our attention will then shift to complexity theory. We will discuss the classes P and NP, as well as NP completeness. How to deal with intractible problems via approximation and using randomness will be considered as well as uses of intractibility such as cryptography. Finally, various kinds of lower bound arguments in circuit complexity will be presented.

Below is a tentative time table for when we'll do things this quarter:

When I assign grades the high score has an opportunity to receive an A+. I do curve grades and my curving will be in line with previous times this class has been taught. If you do better than an A- in this class and want me to write you a letter of recommendation, I will generally be willing.

Links to the current list of assignments can be found on the left hand frame of the class homepage. A link that will allow you to view your grades for the course can also be found here.

Homeworks are required to be done in groups of two to three people. Homeworks with fewer than two or more than three names on them will not be accepted. Homeworks must be written up neatly on paper and are always due by the start of class on the due date. Late homeworks will not be accepted; however, your low homework score will be dropped. The names of the people who worked together on the assignment must be clearly written on the upper right corner of the first page. If I cannot read a name that person will not receive any credit on that homework set. Each homework will consist of a reading and writing part. Material from the reading part of an assignment may appear on midterms and finals.

As each homework set will consist of many problems it is recommended that you divide the labour of doing the problems among the members of the group. You are allowed to change groups after each homework provided that you still remain in groups of two or three. On the day a homework is due, I will invite each group to write a problem on the board. I will grade this problem at that time. Students can copy down what is on the board as a solution set for that homework. If there is anything ambiguous about a problem that has been written on the board I will choose a random member to the group who wrote the problem on the board to ask for clarification. It is each group member's responsibility to make sure the other group members know how to do all the problems on a given homework set.

The midterms will be during class time on: Mar 5 and Apr 21.

The final will be: Monday, May 19 from 5:15pm to 7:30pm.

All exams are closed book, closed notes and in this classroom. You will be allowed only the test and your pen or pencil on your desk during these exams. Beeper or cell-phone interruptions will result in immediate excusal from the test. The final will cover material from the whole quarter although there will be an emphasis on material after the last midterm. No make ups will be given. The final exam may be scaled to replace a midterm grade if it was missed under provably legitimate circumstances. These exams will test whether or not you have mastered the material both presented in class or assigned as homework during the quarter. My exams usually consist of a series of essay style questions. I try to avoid making tricky problems. The week before each exam I will give out a list of problems representative of the level of difficulty of problems the student will be expected to answer on the exam. Any disputes concerning grades on exams should be directed to me, Professor Pollett.

If you believe an error was made in the grading of your program or exam, you may request in person a regrade from me, Professor Pollett, during my office hours. I do not accept e-mail requests for regrades. A request for a regrade must be made no more than a week after the homework is returned.