CS154: Introduction to Automata and Complexity Theory

Spring 2009-10 Course Information

General 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.

  • Honor Code and Collaboration Policy: Under the honor code of Stanford, each of you is expected to submit your own work in this course.

    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 Honor Code.

    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 other students.

  • 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.