CS154 Introductory Information


Finding This Document
Course Goals
Time and Place
Course Personnel and Office Hours
Course Texts
Email Help
Course Mailing List
Course Project
Grading Policy
The Honor Code

Finding This Document On-Line

The class Web page is http://www.stanford.edu/class/cs154. You can find a link to this document and all other course material there. This introductory material can be obtained directly as: http://www.stanford.edu/class/cs154/intro.html Note that this and the outline page are ``living documents''; they can be expected to change during the quarter, and the ``official'' contents are whatever the on-line version has, not the hardcopy handed out at the beginning of the course.

This and other documents can be found in hardcopy form at the ``handout hangout'' between the A and B wings on the 4th floor of Gates. Whatever is not picked up in class will appear there, but we shall not restock the supply once it is gone.

Course Goals

There are two purposes to this course. One is to give you an understanding of some useful concepts that are considered ``theoretical'': models for computation such as finite automata and Turing machines. In something of a departure from previous editions of CS154, there will be some effort to convince you that this technology is important for implementing a variety of the latest types of software, e.g., information consolidators for the Web.

The other goal is to give each student a sense of how to reason formally about computing, how to prove theorems about computation, and how to tell rigorous proof from wishful thinking.

Time and Place

The class meets Mondays and Wednesdays 3:15PM - 4:30PM, Bldg. 370; Rm. 370.

There will be optional sections at 4PM (in Room 380-380W) and 7PM (in Room 380-380C) Tuesdays, starting 1/11.

Course Personnel

PersonRoleOfficePhoneOffice HoursEmail
Jeffrey D. UllmanInstructor 411 Gates(650) 725-4802 MWF 11AM--noon ullman @ cs.stanford.edu
Nathan Folkert TA TBD B12 Gates 7-10PM Sundays except Sunday Jan. 16 - rescheduled for Monday Jan. 17 7-10PM Gates B12 nfolkert @ leland.stanford.edu
Daniel Chai TA 193C Gates (650) 725-3208 9-11AM Mondays, 3-4PM Thursdays dchai @ cs.stanford.edu
Marianne Siroker Course Secretary436 Gates(650) 723-0872N/Asiroker @ db.stanford.edu


CS 109 (introductory CS theory) or equivalent. Unlike previous editions of CS154, there will be a project component to this course, so students should be comfortable with writing significant programs in C or C++. Please discuss the matter with the instructor if you are not sure you have the needed background.

Course Reader

A new edition of Hopcroft and Ullman Introduction to Automata Theory, Languages, and Computation is in devlopment, and we shall be using the notes from this book as a text. It is available at the bookstore at cost.

Email Consulting

If you need a quick answer to a question, try sending email to cs154-help @ lists.stanford.edu. This list forwards to the TA's and instructor, and with luck you'll get a reply in a few minutes.

Class Mailing List

We shall use a class mailing list, cs154-all @ lists. You should send the message
subscribe cs154-all
to majordomo @ lists.stanford.edu. The message should come from your preferred mail-reading host.

We hope that messages to this list will be limited to notes of general interest to the class. In most circumstances, you should use the cs154-help list mentioned above in order to have a question about the course material answered.

Also, do not try to subscribe to the cs154-help list if you are not a TA for the class.

Course Requirements


Further details will be given in the first weeks of the course, but the general idea is for students to write a regular-expression processor, and then use it to mine a large body of text for information of some type, by figuring out the patterns in which the information is likely to appear and specifying the pattern(s) by regular expressions.


Homeworks will generally be due on Mondays at the beginning of class. If you do not wish to attend class, you can bring it to Ms. Horn before the class begins. Work handed in afer 3:15PM will be considered late, and see below...

No late homeworks will be accepted. However, since there are occasional emergencies, each student is allowed one extension of at most 48 hours. This amount of time cannot be divided among assignments; it applies to one assignment only.


There will be a midterm and a final. The final is on March 15, at 12:15PM - 3:15PM. Please do not plan to leave campus before the final, as I never give early exams and am very unsympathetic to people who want to defer the exam until the next quarter.

Grading Policy

The approximate weights of the four components are:


Honor-Code Policy

The basic presumption is that the work you do is your own. Occasionally, especially when working problem sets or writing programs (but never on exams!), it may be necessary to ask someone for help. You are permitted to do so, provided you meet the following two conditions.
  1. You acknowledge the help on the work you hand in.

  2. You understand the work that you hand in, so that you could explain the reasoning behind the parts of the work done for you by another.

Any other assistance by another person constitutes a violation of the honor code and will be treated as such.

Also a violation of the HC is an attempt to make your project appear to do things it cannot do. That is, output must be from the code that is handed in. In the recent past, I've noticed an increase in cases where people were careless about what version of their program they hand in. Please be sure you hand in your final version; an old version coupled with output it could not possibly generate looks to us like an HC violation and will be treated as such.

We shall not deduct credit for small amounts of acknowledged assistance. Even working as a team on one of several problems in a problem set may not hurt your grade, as long as all members of the group acknowledge their collaboration. Such shared interest can be beneficial to all concerned. We do reserve the right to give less than full credit in circumstances where it appears that there has been large-scale division of labor, and you are not getting as much learning out of the assignment as you should. However, as long as you acknowledge your sources, you cannot get into Honor-Code trouble.

If you have any questions about what this policy means, please discuss the matter with the instructor now.