CS154: Automata and Complexity Theory, Winter 2015

[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

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

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

TAs:

• Brynmor Chapman, chapmanb (at stanford dot edu)
• Mikaela Grace, mgrace (at stanford dot edu)
• Kevin Lewi, klewi (at cs dot stanford dot edu)

Class: Tuesday-Thursday 12:50-2:05, Gates B3

Office hours:

• Ryan: Friday 3:30pm-5:30pm, Gates 464
• Brynmor: Monday 12pm-2pm, Gates 460
• Mikaela: Tuesday 10-12pm, Gates B28
• Kevin: Monday 3pm-4pm and Thursday 2:15-3:15pm, Gates 492

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

Textbook:

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

Homeworks:

• Homework comes out on Tuesdays and will be due the following Tuesday at 11:59pm. 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 or the TAs 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-win15-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, from 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: To request a regrade, please send a (scanned) PDF of your graded pset in an email to me and the TAs, along with detailed remarks about why you think you deserve more points. (If you have a smartphone, we recommend CamScanner for easy scanning and PDF creation.) Be warned that the TAs may wish to regrade the entire pset, not just the problems under dispute. We require that you submit your request within two weeks after the homework/exam is returned.

• For all homework questions (that do not give away solutions!), please post to piazza.com/stanford/winter2015/cs154 or visit us at office hours. You can also send private questions (to TAs and instructors only) using Piazza.

Lectures

• 01/8 Introduction and summary of the course; intro to finite automata, DFAs and NFAs
  Readings: Sipser, Chapter 0, 1.1
  Slides (in handout form): [color pdf] [grayscale pdf]
  

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

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

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

• 01/27 Streaming algorithms and communication complexity
  Readings: Luca Trevisan's notes on streaming algorithms
  [Optional reading] A nice Communications of the ACM article on finding frequent elements
  Slides: [color pdf] [grayscale pdf]
  

• 01/29 Finish up communication complexity, Turing machines
  Readings: Sipser Chapter 3, and Turing's amazing paper (also here)
  [Optional reading] A survey by Alexander Razborov on communication complexity
  Slides: [color pdf] [grayscale pdf]
  

• 02/03 Decidability, Recognizability, and Diagonalization
  Readings: Sipser 4, 5.1, 5.2
  Slides: [color pdf] [grayscale pdf]
  

• 02/05 Diagonalization, Undecidability, and Reductions
  Readings: Sipser 5.2, 5.3
  Slides: [color pdf] [grayscale pdf]
  

• 02/10 More on Reductions, and Rice's Theorem
  Readings: Sipser 6.1, Luca Trevisan's notes
  Slides: [color pdf] [grayscale pdf]
  

• 02/12 Computability and the Foundations of Mathematics
  Readings: Sipser 6.3, 6.1, 6.2
  Slides: [color pdf] [grayscale pdf]
  

• 02/17 Midterm (In Bishop Auditorium)
  

• 02/19 Kolmogorov Complexity
  Readings: Sipser 6.4
  Slides: [color pdf] [grayscale pdf]
  

• 02/24 Time Complexity, Time Hierarchy Theorem, P and NP
  Readings: Sipser 7.1, 7.2, 7.3, 9.1
  Slides: [color pdf] [grayscale pdf]
  

• 02/26 Polynomial-Time Reductions, The Cook-Levin Theorem
  Readings: Sipser 7.4, Luca Trevisan's proof of Cook's Theorem
  Slides: [color pdf] [grayscale pdf]
  

• 03/03 More on Cook-Levin, NP-completeness of Clique, Independent Set, Vertex Cover
  Readings: Sipser 7.5
  Slides: [color pdf] [grayscale pdf]
  

• 03/05 NP-completeness of Subset Sum, Knapsack, Partition, Bin Packing, coNP
  Readings: Sipser 7.5, Luca Trevisan's notes
  Slides: [color pdf] [grayscale pdf]
  

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

• 03/12 PSPACE, PSPACE-complete problems, course summary
  Readings: Sipser 8.1, 8.2, 8.3
  Slides: [color pdf] [grayscale pdf]
  

• Study for the final exam!

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]

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.