CS154: Automata and Complexity Theory, Winter 2014

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



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: Tuesday-Thursday 2:15-3:30, Gates B3

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 perfectly fine for this course, if you can find it cheaper.

Grading: Midterm exam: 20%, Final exam: 30%, Homework: 50%.



so far: what's ahead:


Homework comes out on Thursdays and is due the following Thursday, at the beginning of class. (EXCEPT FOR HOMEWORK 6!)

They will (eventually) be posted here.

  1. Homework 1 is due Jan 16. Avg: 13.09, Median: 14, StdDev: 3.09
  2. Homework 2 is due Jan 23. Avg: 13.36, Median: 14, StdDev: 1.29
  3. Homework 3 is due Jan 30. Avg: 16.16, Median: 18, Stddev: 4.74
  4. Homework 4 is due Feb 6. Avg: 13.03, Median: 14, Stddev: 4.84
  5. Homework 5 is due Feb 20. Avg: 14.03, Median: 17, Stddev: 6.03
  6. Homework 6 is due Mar 6.
  7. Homework 7 is due Mar 13.


The midterm was in-class, on Thursday, February 13. For this exam, we allowed one single-sided sheet of notes (on the usual 8.5x11 letter paper); otherwise, the exam was closed-book.

According to this calendar, the final exam will be held March 17th, 3:30-6:30pm in Skilling Auditorium. For this exam, we will allow one double-sided sheet of notes; otherwise, the exam is closed-book.