Chris Pollett >Old Classes >

( Print View )

Grades: [Sec1]

Course Info:
Texts & Links]
  [HW Info]
  [Exam Info]

HW Assignments:
  [Hw1]  [Hw2]  [Hw3]
  [Hw4]  [Hw5]

Practice Exams:
  [Mid1]  [Mid2]  [Final]


CS254Spring 2003Sec1Home Page/Syllabus

Theory of Computation

Instructor: Chris Pollett
Office: MH 214
Phone Number: (408) 924 5145
Office Hours:MW 2:30-4:00pm F 2:30-4:30pm
Class Meets:
Sec1 MW 5:30pm-6:45pm in MH222


To take this class you must have taken: CS154 with a grade of C- or better.

Texts and Links

Required Texts: Computational Complexity.. by C. Papadimitriou.
Online References & Other Links: comp.theory.


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:

Week 1: Jan 22, Jan 24 Read Ch 1
Week 2: Jan 27, Jan 29 Read pp19-32.
Week 3: Feb 3, Feb 5 Finish Ch 2
Week 4: Feb 10, Feb 12 Read Ch 3
Week 5: Feb 17, Feb 19 Read Ch 4
Week 6: Feb 24, Feb 26 Read Ch 7
Week 7: Mar 3, Mar 5 Read Ch 8
Week 8: Mar 10, Mar 12 Read Ch 9
Week 9: Mar 17, Mar 19 Read Ch 10 (then Spring recess)
Week 10: Mar 31(Holiday), Apr 2, Apr 4 Read pp241-259
Week 11: Apr 7, Apr 9 Finish Ch 11
Week 12: Apr 14, Apr 16 Read Ch 12
Week 13: Apr 21, Apr 23 Read pp329-339
Week 14: Apr 28, Apr 30 Finish Ch14
Week 15: May 5, May 7 Read 17.1-17.2
Week 16: May 12 Review.
The final will be Monday, May 19 from 5:15pm to 7:30pm


Homeworks 40%
Midterm 1 15%
Midterm 2 15%
Final 30%

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.

Homework Info

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.

Academic Honesty

Plagiarism on homework or cheating on tests will result in appropriate academic disciplinary action being taken. Information on the university policy governing academic dishonesty can be found at