CS154: Introduction to Automata and Complexity Theory
Spring 2009-10 Course Information
Class URL: The class webpage is http://www.stanford.edu/class/cs154 where all material will be posted.
Lectures: Tuesday-Thursday 2:15 PM -- 3:30 PM in Gates B01.
Instructor: Jeffrey D. Ullman (ullman AT gmail DT com). Office: Gates 433.
Admin: Marianne Siroker (siroker AT cs.stanford.edu). Office: Gates 435.
Teaching Assistants: Shrey Gupta, Rohan Jain, Jia Li
Textbook: The textbook for the class will be Introduction to
Automata Theory, Languages, and Computation by Hopcroft, Ullman and Motwani.
Copies are available from the bookstore.
You should get the 3rd Edition, which comes with the Gradiance access card.
If you don't want to buy the text or buy a used copy without the card, you will need
to go to The Addison-Wesley Website to
purchase access on-line.
CS154N: CS154N students should attend lectures on Turing machines and
NP-completeness. Note that the calendar is only approximate, so the lectures
might happen a little earlier or later than scheduled.
Graded work for CS154N consists of homework problems based on Chapters 8-11 of the text
and a portion of the final exam based on that material.
Grading Policy: We shall assign regular Gradiance (automatically graded and tutored)
homeworks that you do on-line. In addition, you will be expected to do several written
problem sets ("challenge problems"), often involving proofs.
There will be a midterm and a final.
Grades will be based on:
Gradiance homeworks (20%), Challenge Problems (20%), Midterm (20%), Final (40%).
Homework Policy: Gradiance homeworks must be completed by the due date.
For challenge problems, you have a total of 4 late days, but can use only two of
them on any one assignment.
If you do not wish to bring homework to class for collection, you can hand them to
Ms. Siroker in 435 Gates before the class begins.
Only medical excuses can be used to abrogate these rules.
Signing Up For Gradiance:
The class token for our CS154 class is 1DC79FE7.
Register it at www.gradiance.com/pearson.
Texts come with free access cards.
Go to www.aw-bc.com/gradiance
to purchase an access code or to register (link at upper left) the access that came with your text.
Under the honor
code of Stanford, each of you is expected to submit your own work in this
You must acknowledge any sources you use to solve problems, other than
the class textbook. This statement includes both materials found on
the Web or elsewhere and help from other people, students or not.
It is ok to receive hints and debugging help from the instructor, TA's,
or other students, or to have general discussions about
problem solving strategies and write-ups, but you must indicate
clearly on your assignment any assistance you received. Any
assistance received (both from human and from inanimate sources) that
is not given proper citation may be considered a violation of the
In any case, you are responsible for understanding and being able to
explain all of the statements in your assignments and examinations.
Solutions must be written up independently of
Reading Assignments: The required reading will cover the material presented in class, and the
suggested reading will cover background/additional material. The
readings will be drawn from the course textbook.
Assigned sections should be read (at least quickly) before the lecture.