Introduction to Automata and Complexity Theory - Winter 2001
- MW 3:15-4:30. Jan 10 - Mar 14; not on Jan 15 and Feb 19 (i.e. 17 sessions)
- Discussion hours with TA: Fridays 2:15-3:30pm in
lecture room 380Y (in the basement, right in front of the
- 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.
- Rob van Glabbeek,
tel. 723-4405. Email: rvg@cs
- Office hours: Monday & Wednesday 1:30-2:30pm, or right after class.
- Stephen Lindholm,
Office B26 in basement of Gates,
- Office hours: Monday 11:30am-1:00pm and Tuesday 11:00am-12:30pm.
- Sriram Sankaranarayanan,
tel. 723-4638. Email: srirams@cs
- Office hours: Tuesdays 9-10:45 am and Fridays 3:45-5:30pm.
- Email, reaching me and both TAs:
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 non-context 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, NP-completeness.
- CS103 (A & B, or X).
- 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,
- Midterm: Friday, Feb. 9 from 2:45 to 5:15pm in
- Final: Thursday, March 22 from 12:15 to 3:15pm in
- 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.
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.
- change of pace: focus on one problem
- occasional exposure to the business end
- free up TAs for more interactive assistance
- Class mailing list:
Subscribe by sending an email to firstname.lastname@example.org
with the message "subscribe cs154-class" 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:
- 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