Announcement
- <2022-09-19 Mon> Syllabus is posted. Check below.
- <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: R 15:20 - 16:20 (FAB 120-25 and Zoom).
- TA: Mehil Agarwal (mehil@pdx.edu). Office hours: T 12:50 - 13:50, F 11:00 - 12:00 (Fishbowl and Zoom).
- 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.