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
Class: Monday and Wednesday 4:30-5:50, Skilling Auditorium
Office hours:
Ryan: Friday 10am-12pm, Gates 464
Cody: Wednesday 10am-12pm, Gates 488
Lera: Tuesday 12pm-2pm, Gates 494
Sunny: Tuesday 6-8pm, basement of Huang
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.
Michael Sipser, Introduction to the Theory of Computation (3rd Edition), Thomson
Note: the 2nd edition of Sipser is also fine for this course, if you can find it cheaper!
Grading: Midterm exam: 25%, Final exam: 30%, Homework: 45%.
Homeworks:
Homework comes out on Wednesdays and will be due the following Wednesday 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 or the TAs about it (ASAP).
Policy on Collaboration:This is very important; please read carefully. We believe that the best learning often happens when you work with others, and we want to encourage that. But it is equally important that you try to learn on your own! So here are our rules for collaboration on homework:
You must think about all homework problems on your own and do your very best to find the solutions yourself, before discussing/collaborating with other students. After failing to find the answers yourself, you may discuss homework problems with other students, and work in groups on the remaining questions.
You must not look for solutions on the web. Instead, ask questions on Piazza if/when you get stuck.
Cite properly! If you work in a group, include the names of the other people in the group in your written solution. In general, if you do receive a significant idea from someone or somewhere, you must acknowledge that person/book/website in your solution.
You must write up your own solution to every problem; you may not copy answers from another student, or any other source. Also, you may not show your answers to another student. Failing to follow this rule may constitute plagiarism.
Deviating from the above rules may result in an honor code violation. If you have any questions about our policy, please don't hesitate to send a private note to the course staff on Piazza. We have these rules so that you can learn on your own, and also learn from your classmates. They're actually pretty lax compared to other courses, so please respect them!
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 and it is hand-written, 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). In any case, please name your file FirstnameLastname-HW#.pdf (for example: AlanTuring-HW3.pdf) and email to cs154-win16-submissions@lists.stanford.edu from a stanford email address.
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. Note, this does not mean your proofs should be long -- in fact, typically, good clear explanations are also short!
Regrade Policy: 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.
For all homework questions (that do not give away solutions!), please post
to piazza.com/stanford/winter2016/cs154 or visit us at office hours. You can also send private questions (to TAs and instructors only) using Piazza.
01/27 More on 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]
Midterm: The midterm was in-class, on Wednesday, February 17. For this exam, we allowed one single-sided sheet of notes (on the usual 8.5x11 letter paper).
Final:According to this webpage, the final exam will be Friday, March 18, 3:30-6:30pm. NOTE: This time slot is for courses starting at 4:30pm on any day, so beware of taking Tuesday-Thursday 4:30 courses! For this exam, we will allow one double-sided sheet of notes; otherwise, the exam is closed-book.
