Princeton University

Computer Science 487


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:008: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 78 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
Formal models of computation: Finite Automata and Turing Machines. Universality Theorem and the ChurchTurning Thesis. Computability Theory ("What can or cannot be computed?") and Complexity Theory ("How efficient can a certain computation be?"). NPcompleteness and PSPACE completeness.
Here is an Information sheet about the course. Info Sheet COS487
Lectures: TTH 15001620, Room: 302, CS Building
Professor: Sean Hallgren, 307 CS Building,
Undergraduate Coordinator: Donna O'Leary  410 CS Building  2581746
Teaching Assistants: Siddhartha Brahma  001C CS Building  2587418 Office Hours: 4:00 to 6:00 pm, Wednesday
Precepts: Every Tuesday, 7:008:00 pm, Room 301 CS Building
Textbook: Introduction to the Theory of Computation by Michael Sipser, 2nd Edition, PWS Publishing Co.
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 midterm and a take home endterm exam.
Grades: 50% Assignments, 15% MidTerm, 35% EndTerm.
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 preexisting solutions from these sources, or using solution material from the Web is not allowed.