**[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.**

**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,. 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).*we will drop the lowest homework grade in computing your final grade* -
**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.

- 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!

They will (eventually) be posted here.

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