CS154

Introduction To Automata And Complexity Theory - Winter 1996

Time:

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 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. 723-4405. Email: rvg@cs

Office hours: Monday & Wednesday 1:30-2:30pm, or right after class.

TAs:

Harish Devarajan, Gates 490, tel. 725-3110. Email:harish@cs

Office hours: Monday 11:15-12:15 & Friday 9-10 in Gates 193C.

Nikolaj Bjørner, Gates 460, tel. 723-1809. Email: nikolaj@cs

Office hours: Tuesday & Thursday 4-5 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 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. Alternate: 254. Prerequisite: 109B.

Textbook:

R.W. Floyd & R. Beigel (1994): The Language of Machines, Computer Science Press (Freeman).

Coverage:

The whole text (Chapters 0-9),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.