CS154 - Automata and Complexity Theory - Winter 2016
Stanford CS

[General Info]   [Lectures]   [Homeworks]   [Exams]

Announcements on Piazza


What is computation? Given a definition of a computational model, what problems can we hope to solve in principle with this model? Besides those solvable in principle, what problems can we hope to efficiently solve? This course provides a mathematical introduction to these questions. In many cases we can give completely rigorous answers; in other cases, these questions have become major open problems in both pure and applied mathematics!

By the end of this course, students will be able to classify computational problems given to them, in terms of their computational complexity (Is the problem regular? Not regular? Decidable? Recognizable? Neither? Solvable in P? NP-complete? PSPACE-complete?, etc.) They will also gain a deeper appreciation for some of the fundamental issues in computing that are independent of trends of technology, such as the Church-Turing Thesis and the P versus NP problem. Prerequisites: CS 103 or 103B.

General Information



Class: Monday and Wednesday 4:30-5:50, Skilling Auditorium

Office hours:

Rather than emailing questions directly to the teaching staff, we encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.

Sign up with Piazza to stay updated on the course!


Note: the 2nd edition of Sipser is also fine for this course, if you can find it cheaper!

Grading: Midterm exam: 25%, Final exam: 30%, Homework: 45%.



[Jump to What's Ahead]



Homework comes out on Wednesdays and is due the following Wednesday.
  • Homework 1 is due Jan 13. [latex source] Avg: 12.09 out of 15, StdDev: 2.93
  • Homework 2 is due Jan 20. [latex source] Avg: 11.52 out of 14, StdDev: 2.44
  • Homework 3 is due Jan 27. [latex source] Avg: 14.1 out of 16, Stddev: 1.8
  • Homework 4 is due Feb 3. [latex source] Avg: 14.6 out of 18, Stddev: 4.026
  • Homework 5 is due Feb 10. [latex source]. Avg: 14.49 out of 17, Stddev: 2.49
  • Homework 6 is due Mar 2. [latex source].
  • Homework 7 is due Mar 9. [latex source].

  • Exams

    Midterm: The midterm was in-class, on Wednesday, February 17. For this exam, we allowed one single-sided sheet of notes (on the usual 8.5x11 letter paper).

    Final: According to this webpage, the final exam will be Friday, March 18, 3:30-6:30pm. NOTE: This time slot is for courses starting at 4:30pm on any day, so beware of taking Tuesday-Thursday 4:30 courses! For this exam, we will allow one double-sided sheet of notes; otherwise, the exam is closed-book.