CS154

 Notes Homework

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.
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 latter part of the course only (named CS154N); this yields 2 units.
Instructor:
Rob van Glabbeek, Gates 478, tel. 723-4405. Email: rvg@cs.stanford.edu
Office hours: Monday & Wednesday 1:15-2:15pm, or right after class.
TAs:
Aaron Bradley, Email: arbrad@stanford.edu
Office hours: Monday 7:00-9:00pm in Gates B24A (725-4385).
Eric Ketchum, Email: ketch22@cs.stanford.edu
Office hours: Friday 11:00am-1:00pm in Gates B24B (736-1816).
Arun Kishan, Email: akishan@cs.stanford.edu
Office hours: Thursday 3:00-5:00pm in Gates B26A (723-6319).
Elena Nabieva, Email: lena@stanford.edu
Office hours: Tuesday 1-3 pm in Gates B26A (723-6319).
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, 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.
Homework: 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 "Extra Credit". 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.
Homework grading plan:
Grading work is distributed across the class. Every student is expected to participate in grading at least once (normally exactly once).
Rationale: 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 entire quarter. We have an outline of what your involvement with grading will be like.
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:
http://kilby.stanford.edu/~rvg/154/.
Class mailing list:
cs154-class@lists.stanford.edu
Subscribe, starting April 3, by sending an email to majordomo@lists.stanford.edu 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.
Newsgroup:
su.class.cs154.
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: cs154@cs.stanford.edu
This is a suitable medium to ask questions that are unsuitable for the newsgroup, when you cannot ask them in person at an office hour.
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.
Rob van Glabbeek rvg@cs.stanford.edu