CS154: Automata and Complexity Theory, Winter 2015

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


Announcements on Piazza

Introduction

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

(NOTE: This course begins on Thursday, January 8th. Typically it is Tuesday-Thursday, 12:50pm-2:05pm, Gates B3.)

Instructor:

TAs:

Class: Tuesday-Thursday 12:50-2:05, 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.

You must sign up with Piazza to stay updated on the course. (CLICK HERE)

Textbook:

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

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

Homeworks:


Lectures

So Far: What's Ahead:


Homework

Homework comes out on Tuesdays and is due the following Tuesday, at 11:59pm.
  1. Homework 1 is due Jan 20. [latex source] Avg: 10.6, StdDev: 4.8
  2. Homework 2 is due Jan 27. [latex source] Avg: 11.2, StdDev: 4.9
  3. Homework 3 is due Feb 3. [latex source] Avg: 10.0, StdDev: 5.8
  4. Homework 4 is due Feb 10. [latex source] Avg: 13.9, StdDev: 3.5
  5. Homework 5 is due Feb 24. [latex source] Avg: 16.1, StdDev: 2.74
  6. Homework 6 is due Mar 3. [latex source]
  7. Homework 7 is due Mar 10. [latex source]


Exams

The midterm was during class time in Bishop Auditorium (Lathrop Library (08-350) 518 Memorial Way), on Tuesday, February 17. For this exam, we will allow one single-sided sheet of notes (on the usual 8.5x11 letter paper); otherwise, the exam is closed-book.

According to this calendar, the final exam will be held Thursday March 19th, 07:00-10:00pm in Hewlett 200 (across the street from Gates). For this exam, we will allow one double-sided sheet of notes; otherwise, the exam is closed-book.