COS 487: Theory of Computation

Formal models of computation: finite automata and Turing machines. Universality Theorem and the Church-Turing Thesis. Computability Theory ("What can or cannot be computed?") and Complexity Theory ("How efficient can a certain computation be?"). NP-completeness and PSPACE-completeness. An introduction to complexity issues in application areas such as robotics, graphics, compilers, and computer security.

Fall 2012

Lectures: Monday,Wednesday, 1:30-2:50
Location: Computer Science 105

Robert Tarjan

  • homepage: link
  • office hours: Monday 3:00-5:00.
  • office: Computer Science 324
  • extension: 4797
  • email: ret at cs dot princeton dot edu, prof dot tarjan at gmail

    • Assistant: Katherine Edwards

  • office hours: Tuesday 1:00-3:00 and by appointment.
  • office: Computer Science 313
  • email: ke at princeton dot edu

    • Assignments

  • Assignment 1 (due September 26, 1:30 PM)

  • Assignment 2 (due October 10, 1:30 PM)

  • Assignment 3 (due October 24, 1:30 PM)

  • Assignment 4 (due November 21, 1:30 PM)

  • Assignment 5 (due December 12, 1:30 PM)

  • Final Problem Set (updated version) (due January 21, 1:30 PM)

    • Tutorial Paper

  • Tutorial Paper (due Dean’s Date, Tuesday Jan.,15, 2013 / title, short description, and a preliminary list of references due on Monday December 3)

    • Notes

  • Notes on the Recursion Theorem

  • NP-Completeness of the Hamiltonian Cycle Problem