CS154: Automata and Complexity Theory, Winter 2014

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

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

Instructor:

• Ryan Williams, Gates 464, 650 723 6690, rrw at cs dot stanford dot edu

TAs:

• Daniel Hollingshead, dhollingshead at stanford dot edu
• Michael Kim, michael.kim at cs dot stanford dot edu

Class: Tuesday-Thursday 2:15-3:30, Gates B3

Office hours:

• Ryan: Monday 11:00am-12:00pm and 4:30pm-5:30pm, Gates 464
• Daniel: Tuesday 5:00pm-7:00pm, Basement of Huang (announced on Piazza)
• Michael: Wednesday 4:15pm-6:15pm, Gates B28

Sign up with Piazza to stay updated on the course!

Textbook:

• Michael Sipser, Introduction to the Theory of Computation (3rd Edition), Thomson

Homeworks:

• Homework comes out on Thursdays and will be due the following Thursday at the beginning of class. No homework will be assigned for the week before the midterm exam. Late assignments will not be accepted. To account for this, we will drop the lowest homework grade in computing your final grade. If you are unable to submit your homework because of extenuating circumstances such as a family/medical emergency, please contact Ryan, Michael, and Daniel about it (ASAP).

• Policy on collaboration: This is very important; please read carefully. We understand that learning often best happens when you communicate with others, and we want to encourage that. But it is equally important that you try to learn on your own. You may discuss homework problems with other students and you may work in groups, but we require that you try to solve the problems by yourself before discussing them with others. Please think about all the problems on your own and do your best to find the solutions, before launching into a collaboration. If you work in a group, you must include the names of the other people in the group in your written solution. You must write up your own solution to every problem; you may not copy answers from another student or any other source. In general, if you receive a significant idea from someone or somewhere, you must acknowledge that person/book/website in your solution. Deviating from this policy may result in an honor code violation; please respect these guidelines.

• How to write/submit homework: Write the solution to each problem on a separate page, and write your name, SUID (the 8-digit number), SUNet ID, homework number, and problem number on top of each page.
  If you are an in-class student, you can (1) hand in your homework in class, (2) drop off your homework in the CS 154 dropbox in the Gates 1B lobby, or (3) email your homework.
  If you are an SCPD student, you can (1) physically mail your homework to your SCPD liason or (2) email your homework to us, cc-ing your SCPD liason.
  If you are emailing your homework, prepare your scanned images into a single pdf file consisting of 8.5x11 pages (or write your solution in LaTeX and compile it to pdf). Please name your file FirstnameLastname-HW#.pdf (for example: AlanTuring-HW3.pdf) and email to cs154-win14-submissions@lists.stanford.edu.

  We encourage you to use LaTeX to compose your homeworks! It is a great system, practically every computer science paper published nowadays is written with it, and it came from Stanford (namely, our own Don Knuth). If you use Windows, MiKTeX is a good choice. If you decide to write your solutions, please write legibly. Your TAs may mark your solution as incorrect if they cannot read your handwriting.

  Most of the work you will turn in will be mathematical proofs of various cool facts. Your proofs should be as clear as possible (which does not mean long -- in fact, typically, good clear explanations are also short)

• Regrades: If you wish to request a regrade on a problem, you will need to prepare a written justification and come to office hours to talk about your solution in person. We require that you submit your request within one week after the homework/exam is returned.

• Piazza: For all homework questions (that do not give away solutions!), please post to piazza.com/stanford/winter2014/cs154
  You can also send private questions (to TAs and instructors only) using Piazza.

Lectures

• 01/7. Introduction and summary of the course; intro to finite automata, DFAs and NFAs
  Readings: Sipser, Chapter 0, 1.1
  Slides (in handout form): [pdf]
  Students: do you like the format of these slide handouts? Let us know (on Piazza) if you'd like them in a different way!

• 01/9 Review of finite automata (cont), equivalence of DFAs and NFAs, regular expressions
  Readings: Sipser 1.1, 1.2, 1.3
  Slides: [pdf]
  

• 01/14 Equivalence of automata and regular expressions; Proving languages are not regular
  Readings: Sipser 1.4
  Slides: [pdf]
  

• 01/16 Minimizing DFAs
  Readings: Luca Trevisan's notes
  Slides: [pdf]
  
• 01/21 The Myhill-Nerode Theorem, Streaming algorithms 1
  Readings: Sipser Problem 1.52 and its solution
  Slides: [pdf]
  

• 01/23 Streaming algorithms 2
  Readings: Luca Trevisan's notes on streaming algorithms
  [Optional reading] A nice Communications of the ACM article on finding frequent elements
  Slides: [pdf]
  

• 01/28 Turing machines
  Readings: Sipser Chapter 3, and Turing's amazing paper
  Slides: [pdf]
  

• 01/30 Decidability, Recognizability, Enumeration, and Undecidability
  Readings: Sipser 4, 5.1, 5.3
  Slides: [pdf]
  

• 02/04 Undecidability, Reductions, and PCP
  Readings: Sipser 5.2, 5.3
  Slides: [pdf]
  

• 02/06 Rice's Theorem and the Recursion Theorem
  Readings: Sipser 6.1, Luca Trevisan's notes
  Slides: [pdf]
  

• 02/11 Computability and the Foundations of Mathematics
  Readings: Sipser 6.2, Luca Trevisan's notes
  Slides: [pdf]
  

• 02/13 Midterm (In Class)
  

• 02/18 Kolmogorov Complexity
  Readings: Sipser 6.4
  Slides: [pdf]
  

• 02/20 Review of P, NP, reductions, time hierarchy theorem
  Readings: Sipser 7.1, 7.2, 7.3, 9.1
  Slides: [pdf]
  

• 02/25 The Cook-Levin Theorem
  Readings: Sipser 7.4, Luca Trevisan's proof of Cook's Theorem
  Slides: [pdf]
  

• 02/27 NP-completeness of clique, vertex cover, independent set and subset sum
  Readings: Sipser 7.5
  Slides: [pdf]
  

• 03/04 NP-completeness of Hamiltonian path, partition, bin packing, coNP
  Readings: Sipser 7.5
  Slides: [pdf]
  

• 03/06 coNP, Oracle Turing machines, P^{NP}, NP^{NP}, start of space complexity
  Readings: Sipser 9.2, 8.2
  Slides: [pdf]
  

• 03/11 PSPACE, Savitch's Theorem, PSPACE-complete problems
  Readings: Sipser 8.1, 8.2, 8.3
  Slides: [pdf]
  

• 03/13 Finish up space complexity, randomized polynomial time (ZPP, RP, BPP), course summary
  Readings: Sipser 10.2
  Slides: [pdf]
  

• Study for the final!

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.

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.