18.404: Theory of Computation’

Table of contents

  1. Course Info
  2. Realistic Prerequisites
  3. Subject Matter
  4. Course Staff
  5. Lectures
  6. Problem Sets
  7. Exams
  8. Resources
  9. Grading
  10. Advice to Future Students

Course Info

Class Size 218
Hours/Week 10.1 (84 responses)
Instructors Michael Sipser
Overall Rating 6.6/7.0

Realistic Prerequisites

  • Experience with proof-writing is a must.
  • Familiarity with big-O notation and algorithms helped, but wasn’t necessary.

Subject Matter

  • Almost all students agreed that this class is very theoretical.
  • The material covered was broad and foundational, mainly in complexity theory.

Course Staff

  • Approachable and kind, but many students complained that there were not enough TAs.
  • The TAs who were hired put in extra work so that everyone who wanted to meet with them could, though.

Lectures

  • Most students believed that they learned the most from lectures, but found all resources helpful.
  • Many mentioned that the professor was a very engaging presenter.
  • The pacing was just right.

Problem Sets

  • Difficult, but full of interesting problems.
  • Problems required lots of time, and many went to OH for help.
  • Overall, problems were more on the theoretical side.
  • Students took between 4-10 hours per pset, but psets were only assigned every other week.

Exams

  • The one midterm was somewhat difficult and had some time pressure, but most felt the exam was fair.
  • The exam was open book, but required attention to detail.
  • Most of the content came from the lectures.

Resources

  • Almost all students referred to the textbook which the professor wrote, Theory of Computation by Michael Sipser, and it was available online.
  • Some students mentioned that the textbook alone was enough to do well.

Grading

  • Students felt that grading was incredibly fair and reasonable.
  • The late policy for psets was flexible as well.

Advice to Future Students

  1. ”Do the psets early.”
  2. “Take this class!”
  3. ”Go to Office Hours!!”
  4. ”Take this class if you like CS, otherwise I do not recommend it.”
  5. ”Prepare for exams.”