About
- Syllabus:
PDF.
- Instructor: Prof. Fang Song
- Email: fsong “AT” pdx.edu. Start your email subject line
with “f24-581”. Slack is preferred.
- Lectures: MW 14:00 - 15:15 @ EB 92
- Office hours: TBD
- 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.
- 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. Some topics will rely
on lecture notes and additional readings. See Resource
page for useful
materials.