CS154

Introduction to Automata and Complexity Theory - Winter 2001

Time:
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 Building 380; lecture room 380Y (in the basement, right in front of the elevator).
Place:
Building 370; lecture room 370
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:
Stephen Lindholm, Office B26 in basement of Gates, Email: lindholm@cs
Office hours: Monday 11:30am-1:00pm and Tuesday 11:00am-12:30pm.
Sriram Sankaranarayanan, Gates 488, 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:
cs154@cs.stanford.edu
Description:
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.
Prerequisite:
CS103 (A & B, or X).
Textbook:
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, Addison-Wesley, 2000.
Exams:
Midterm: Friday, Feb. 9 from 2:45 to 5:15pm in Building 320; room 105.
Final: Thursday, March 22 from 12:15 to 3:15pm in Building 320; room 105.
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. (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.
Rationale: 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.
Newsgroup:
su.class.cs154.
Class mailing list:
cs154-class@lists.stanford.edu
Subscribe by sending an email to majordomo@lists.stanford.edu 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:
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