Princeton University
Computer Science Department

Computer Science 487
Theory of Computation

Sean Hallgren

Fall 2006

General Information


No Precept on 9/18.

Assignment 1. Due Sept 28 in class. ps pdf

The precept timings have changed. The new timings are Tuesday, 7:00-8:00 pm, Room 102, CS Building.

Assignment 2. Due Oct 5 in class. ps pdf

Assignment 3. Due Oct 12 in class. ps pdf

It seems we cannot use Room 102 for the precept on Tuesday due to a clash. So we will meet in Room 301, CS Building, Tuesday 7-8 pm.

Assignement 4. Due Oct 19 in class. ps pdf

Assignement 5. Due Oct 26 in class. ps pdf

Assignement 6. Due Nov 7 in class. ps pdf

Assignement 7. Due Nov 30 in class. ps pdf

Assignement 8. Due Dec 7 in class. ps pdf

Course Summary

Formal models of computation: Finite Automata and Turing Machines. Universality Theorem and the Church-Turning Thesis. Computability Theory ("What can or cannot be computed?") and Complexity Theory ("How efficient can a certain computation be?"). NP-completeness and PSPACE- completeness.

Here is an Information sheet about the course. Info Sheet COS487

Administrative Information

Lectures: TTH 1500-1620, Room: 302, CS Building

Professor: Sean Hallgren, 307 CS Building,

Undergraduate Coordinator: Donna O'Leary - 410 CS Building - 258-1746

Teaching Assistants: Siddhartha Brahma - 001C CS Building - 258-7418 Office Hours: 4:00 to 6:00 pm, Wednesday

Precepts: Every Tuesday, 7:00-8:00 pm, Room 301 CS Building

Course Material

Textbook: Introduction to the Theory of Computation by Michael Sipser, 2nd Edition, PWS Publishing Co.

Assignments and Exams

Assignments: There will be weekly assigments given on Thursdays in class. They are due in class one week after being assigned.

Exams: There will be a take home mid-term and a take home end-term exam.

Grades: 50% Assignments, 15% Mid-Term, 35% End-Term.

Honor Code

Discussions and collaborations with your classmates on homework assignments are OK, but you must write up your solutions on your own, and you must list your collaborators for each problem; no points will be deducted for collaboration. No collaborations are allowed on examinations. The homework questions are selected for their pedagogical value and may be similar to questions on problem sets from past offerings of this course at Princeton (or some other universities). Using any pre-existing solutions from these sources, or using solution material from the Web is not allowed.