Announcement
- <2022-03-21 Mon> Welcome! Please stay tuned for updates.
About
- 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 xxx.
- 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, assuming a prior introductory
exposure to the theory of computation, continues an in-depth
exploration to these fundamental questions. After reviewing
computability, the focus will be 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. PSU library
link. See
Resource page for
additional useful materials.