Introduction To Automata And Complexity Theory - Winter 1996
- MW 3:15-4:30. Jan 10 - Mar 13; not on Jan 15 and Feb 19 (i.e. 17 sessions)
- Discussion hours (with TAs): Friday 2-3 p.m. in
- Building 420 (Jordan Hall); lecture room 041
- 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, Gates 478,
tel. 723-4405. Email: rvg@cs
- Office hours: Monday & Wednesday 1:30-2:30pm, or right after class.
- Harish Devarajan,
Gates 490, tel. 725-3110. Email:harish@cs
- Office hours: Monday 11:15-12:15 & Friday 9-10 in
Bjørner, Gates 460,
tel. 723-1809. Email: nikolaj@cs
- Office hours: Tuesday & Thursday 4-5 p.m. in
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 non-context free. Turing machines;
equivalent forms, undecidability. Nondeterministic Turing machines:
properties, the class NP, complete problems for NP, Cook's theorem,
reducibilities among problems.
- R.W. Floyd & R. Beigel (1994): The Language of
Machines, Computer Science Press (Freeman).
- The whole text (Chapters 0-9),except
small amounts of material to be determined.
Click here for a list of important topics.
- 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
- 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.
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.
- change of pace: focus on one problem
- occasional exposure to the business end
- free up TAs for more interactive assistance
- 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
Rob van Glabbeek