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: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
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
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
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 mid-term and a take home end-term exam.
Grades: 50% Assignments, 15% Mid-Term, 35% End-Term.
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.