(Fall 2022) CS 581 - Theory of computation


  • <2022-09-19 Mon> Syllabus is posted. Check below.
  • <2022-03-21 Mon> Welcome! Please stay tuned for updates.


  • Syllabus: PDF.
  • Instructor: Prof. Fang Song
  • Email: fsong “AT” pdx.edu. Start your email subject line with “f22-581-toc”. Slack is preferred.
  • Lectures: TR 14:00 - 15:15 @ FAB 46
  • Office hours: xxx
  • TA: xxx. Office hours: xxx.
  • Google classroom: join with code o7qc2p2.
  • Overview: Computation is a familiar term to all computer scientists. But what is computation after all? What problems are computable (Computability), and how “efficient” can we compute them (Complexity)? This course will be investigating these fundamental questions. The discussion on computability will be reviewing and reinforcing what has been covered in a typical undergraduate course on theory of computation. Then we will focus on computational complexity, including time, space, randomness complexity, and selected topics such as interactive proof systems and quantum computing.
  • Prerequisite: CS 311 or equivalent. You need to be familiar with the basics of computability theory, and be comfortable with reading and writing mathematical proofs.
  • Text: [S3] Michael Sipser. Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012. See Resource page for additional useful materials.