Introduction to Automata and Complexity Theory - Spring 2002
- Time & Place:
- MW 3:15-4:30 in Gates B01. April 3 - June 5; not on May 27
(i.e. 18 sessions). CS154N starts on April 24.
- Videos of this class are available from the
SCPD. Regular broadcasts
are on the days of the class from 7:15 to 8:30pm on channel E4.
- Discussion hours with TAs: Fridays 10:00am - 10:50am in the
Skilling Auditorium, starting April 12. Broadcasted live
on channel E3.
- 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 latter part of the course only
(named CS154N); this yields 2 units.
- Rob van Glabbeek,
tel. 723-4405. Email: firstname.lastname@example.org
- Office hours: Monday & Wednesday 1:15-2:15pm, or right
- Aaron Bradley, Email: email@example.com
- Office hours: Monday 7:00-9:00pm in Gates B24A (725-4385).
- Eric Ketchum, Email: firstname.lastname@example.org
- Office hours: Friday 11:00am-1:00pm in Gates B24B (736-1816).
- Arun Kishan, Email: email@example.com
- Office hours: Thursday 3:00-5:00pm in Gates B26A (723-6319).
- Elena Nabieva, Email: firstname.lastname@example.org
- Office hours: Tuesday 1-3 pm in Gates B26A (723-6319).
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, May 3 from 2:45 to 5:15pm in Building 200
(History, if you look from the oval, the very left corner of the
main quadrangle), room 002.
- Final: Tuesday, June 11 from 12:15 to 3:15pm in Gates B03.
- Both exams are open book and open notes.
- Final grades should be available by Thursday, June 13 at noon.
Before submitting the first homework
you should register here.
- Assignments will be posted here on
Wednesdays, due back on the following Tuesday by 5pm.
Here is our late policy.
We plan to post solutions here Thursdays
after 5pm. Corrected homework ends up in a file cabinet in the
4B wing, close to the elevators.
- The homework should be delivered to the fourth floor of the
stairway in the B-wing of the Computer Science building
(i.e. right next to my office).
There you will find 6 boxes, labeled Problem 1, 2, 3, 4, 5 and
Each problem must be on a separate sheet, and the sheets are
to be placed in the appropriate boxes. SCPD students can fax
in their homework through SCPD: (650) 736-1266 or (650)
725-4138, preferbly by 10am, so as to give SCPD a change
to get it to us. For students that cannot come to campus
easily, other delivery methods can be arranged on request.
- The homework sometimes consists of two components: learning
homework and testing homework. Both will be graded,
and the results count for your final grade. To a large extent
both kinds are for learning as well as testing; the difference
is in the collaboration policy.
Usually the homework will contain a difficult optional
extra credit problem. These are mostly for fun, but can be used
to compensate in part for missed homeworks, or failure to
participate in grading. The scores are kept separately, and
only used for your final grade when we are in doubt whether to
round up or down.
- For the learning homework, collaboration is allowed
as long as (1) you acknowledge all the people you discussed
the problem with, and (2) each student writes up his/her own
solution without looking at any writeup/notes from another student.
- The testing homework must be done without any collaboration.
- Homework grading plan:
- Grading work is distributed across the class.
Every student is expected to participate in grading at least
once (normally exactly once).
Roughly three persons (a team) per problem (a
grading atom), and roughly five grading atoms per week.
Teams are formed
by email out
of `volunteers' shortly after 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
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
- Course credit plan:
- Midterm 20%, Final 40%, Homework 35%, Grading 5%.
- Occasionally the homework will contain a difficult optional
extra credit problem, that can be used to compensate in part
for missed homeworks, or failure to participate in grading.
- WWW page:
- Class mailing list:
Subscribe, starting April 3, by sending an email to
email@example.com with the message "subscribe
cs154-class" in the body.
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 homework 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.
- Suitable for any discussion regarding this class. Do not post
hints or solutions to homeworks. This is a good place to ask
(and answer!) general questions about the material (not
containing partial homework solutions). The TAs will monitor
the newsgroup to answer questions.
- Email, reaching me and the TAs:
- This is a suitable medium to ask questions that are unsuitable
for the newsgroup, when you cannot ask them in person at an
- Course notes:
- This file will keep track of the material covered so far, and
list the handouts distributed to date.
- Handouts can be found in the directory handouts.