CS154
Introduction To Automata And Complexity Theory  Winter 1996
 Time:
 MW 3:154:30. Jan 10  Mar 13; not on Jan 15 and Feb 19 (i.e. 17 sessions)
 Discussion hours (with TAs): Friday 23 p.m. in
Gates B08.
 Place:
 Building 420 (Jordan Hall); lecture room 041
 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:
 Harish Devarajan,
Gates 490, tel. 7253110. Email:harish@cs
 Office hours: Monday 11:1512:15 & Friday 910 in
Gates 193C.
 Nikolaj
Bjørner, Gates 460,
tel. 7231809. Email: nikolaj@cs
 Office hours: Tuesday & Thursday 45 p.m. in
Gates 193D.
 Description:

Regular sets: finite automata, regular expressions, equivalences among
notations, methods of proving a language not to be regular. Context
free languages: grammars, pushdown automata, normal forms for
grammars, proving languages noncontext free. Turing machines;
equivalent forms, undecidability. Nondeterministic Turing machines:
properties, the class NP, complete problems for NP, Cook's theorem,
reducibilities among problems.
Alternate: 254.
Prerequisite: 109B.
 Textbook:
 R.W. Floyd & R. Beigel (1994): The Language of
Machines, Computer Science Press (Freeman).
 Coverage:
 The whole text (Chapters 09),except
small amounts of material to be determined.
Click here for a list of important topics.
 Exams:
 Midterm: Friday, Feb. 16 from 2:15 to 5:15pm at the Annenberg
Auditorium in the Cummings Art Building
 Final: Wednesday, March 20 from 12:15 to 3:15pm at Jordan 041
 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.
 Course credit plan:
 Homework 40%, Midterm 25%, Final 35%.
 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 three 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.
 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.
Rob van Glabbeek
rvg@CS.Stanford.EDU