CS154
Introduction to Automata and Complexity Theory  Winter 2001
 Time:
 MW 3:154:30. Jan 10  Mar 14; not on Jan 15 and Feb 19 (i.e. 17 sessions)
 Discussion hours with TA: Fridays 2:153:30pm in
Building 380;
lecture room 380Y (in the basement, right in front of the
elevator).
 Place:

Building 370;
lecture room
370
 Units:
 4 (graduate students may choose to take it for only 3 units; this
does not influence the amount of work to be done). It is also
possible to participate in the second half of the course only
(named CS154N); this yields 2 units.
 Instructor:
 Rob van Glabbeek,
Gates 478,
tel. 7234405. Email: rvg@cs
 Office hours: Monday & Wednesday 1:302:30pm, or right after class.
 TAs:
 Stephen Lindholm,
Office B26 in basement of Gates,
Email: lindholm@cs
 Office hours: Monday 11:30am1:00pm and Tuesday 11:00am12:30pm.
 Sriram Sankaranarayanan,
Gates 488,
tel. 7234638. Email: srirams@cs
 Office hours: Tuesdays 910:45 am and Fridays 3:455:30pm.
 Email, reaching me and both TAs:
 cs154@cs.stanford.edu
 Description:

Regular languages: finite automata, regular expressions, equivalences
among notations, methods of proving a language not to be regular.
Context free languages: context free grammars, pushdown automata,
normal forms for grammars, proving languages noncontext free.
Computability theory: Turing machines, equivalent forms,
recursive and recursive enumerable languages, recursive and partial
recursive functions, Church' thesis, undecidability, diagonalization,
incompleteness, reducibilities among problems.
Complexity theory: time and space complexity classes, the
classes P, NP, and PSPACE, NPcompleteness.
 Prerequisite:
 CS103 (A & B, or X).
 Textbook:
 Michael Sipser:
Introduction to the Theory of Computation, PWS
Publishing Company, 1996.
 Optional alternative textbook: Hopcroft, Motwani & Ullman:
Introduction to Automata Theory, Languages, and Computation,
AddisonWesley, 2000.
 Exams:
 Midterm: Friday, Feb. 9 from 2:45 to 5:15pm in
Building
320;
room 105.
 Final: Thursday, March 22 from 12:15 to 3:15pm in
Building
320;
room 105.
 Homeworks:
 Assignments will be handed out on Wednesdays, due back on the
following Wednesday at the beginning of class. Click
here for our late policy.
 EACH PROBLEM MUST BE ON A SEPARATE SHEET
 The homework must be done without any collaboration.
(Exception: extra credit problems may be done with
collaboration, but on the homework sheet you should mention
everyone who collaborated, so that we know who is to be credited.)
 Course credit plan:
 Homework 40%, Midterm 20%, Final 40%.
 Moreover, every student is required to
participate in grading at least once.
 Occasionally there will be a (difficult) extra credit problem,
that can be used to compensate in part for missed homeworks,
unfinished exams, or failure to participate in grading.
 Homework grading plan:
 Grading work is distributed across the class.
 Rationale:
 change of pace: focus on one problem
 occasional exposure to the business end
 free up TAs for more interactive assistance
Roughly three persons (a team) per problem (a
grading atom), and roughly four grading atoms per week. Teams
are formed out of `volunteers' at the end of class on the day
homeworks are handed out, and team members work with TAs to grade the
homeworks. Each student must anticipate becoming a grader once during
the entire quarter.
We have an outline of what your
involvement with grading will be like.
 Newsgroup:
 su.class.cs154.
 Class mailing list:

cs154class@lists.stanford.edu
Subscribe by sending an email to majordomo@lists.stanford.edu
with the message "subscribe cs154class" in the body. Only
stanford.edu addresses are allowed on the mailing list.
This list is for important announcements to the class, such as
corrections in the given homework. These announcements will also
appear on the webpage notes or handouts and the newsgroup.
Do not post to this list, except in the rare case that
you have urgent information to convey to the class at once.
 WWW page:
 http://kilby.stanford.edu/~rvg/154/.
 Course notes:
 This file will keep track of the material covered so far, and
list the handouts, homeworks and solutions distributed to date.
These can also be found in the handout hang out, located
in the lobby of Gates 4B, and in the directory
handouts.