CS154: Introduction to Automata and Complexity Theory

Spring 2009-10

     [Announcements]    [Course Information]    [Homeworks]    [Lecture Notes]    [Course Staff and Contacts]    [Hours&Locations]



Announcements



Course Information



Exams from This Course



Homework Assignments

Date DueAssignmentSolutions
4/22 midnight Gradiance Assignment #1 (Proofs, Etc.) View your work after the deadline
4/13, 2:15PM Challenge Problems #1 Solution
4/22 midnight Gradiance Assignment #2 (Finite Automata) View your work after the deadline
4/22 midnight Gradiance Assignment #3 (Automata and Regular Expressions)
Note: One problem requires you to know some of the UNIX
regular-expression operators from Section 3.3.1.
View your work after the deadline
4/20, 2:15PM Challenge Problems #2 Solution
4/22 midnight Gradiance Assignment #4 (Closure Properties and CFG's) View your work after the deadline
4/27, 2:15PM Challenge Problems #3 Solution
4/29 midnight Gradiance Assignment #5 (Parse Trees, Normal Forms) View your work after the deadline
5/6 midnight Gradiance Assignment #6 (Pushdown Automata) View your work after the deadline
5/11, 2:15PM Challenge Problems #4 Solution
5/13 midnight Gradiance Assignment #7 (Context-Free Languages) View your work after the deadline
5/18, 2:15PM
required for CS154 and CS154N
Challenge Problems #5
5/20 midnight
required for CS154 and CS154N
Gradiance Assignment #8 (Turing Machines) View your work after the deadline
5/27 midnight
required for CS154 and CS154N
Gradiance Assignment #9 (Undecidable Problems) View your work after the deadline
6/1, 2:15PM
required for CS154 and CS154N
Challenge Problems #6
6/3 midnight
required for CS154 and CS154N
Gradiance Assignment #10 (Intractable Problems) View your work after the deadline
6/3 midnight
required for CS154 and CS154N
Gradiance Assignment #11 (NP-Complete Problems) View your work after the deadline
6/3 midnight
required for CS154 and CS154N
Gradiance Assignment #12 (Tougher NP-Complete Problems) View your work after the deadline
6/4 midnight
Optional, will not count
in your grade
Optional Gradiance Assignment (Inductive Proofs) View your work after the deadline

Lecture Notes


DateSubjectSlidesReadings
3/30 Course Introduction PPT, PDF Chapter 1
3/30 Introduction to Automata PPT, PDF Section 2.1
3/30, 4/1 Deterministic Finite Automata PPT, PDF Section 2.2
4/1, 4/6 Nondeterministic Finite Automata PPT, PDF Sections 2.3 - 2.5
4/6 Regular Expressions PPT, PDF Chapter 3
4/8, 4/13 Decision Properties of Regular Languages PPT, PDF Sections 4.1, 4.3, 4.4
4/13 Closure Properties of Regular Languages PPT, PDF Section 4.2
4/15 Context-Free Languages PPT, PDF Section 5.1
4/15, 4/20 Parse Trees PPT, PDF Sections 5.2, 5.4
4/20, 4/22 Normal Forms for Context-Free Grammars PPT, PDF Section 7.1
4/22 Pushdown Automata PPT, PDF Sections 6.1, 6.2
4/22, 4/27 Equivalence of CFG's and PDA's PPT, PDF Section 6.3
4/27 The Pumping Lemma for Context-Free Languages PPT, PDF Section 7.2
4/27, 4/29 Properties of Context-Free Languages PPT, PDF Sections 7.3, 7.4
4/29, 5/6 Enumerations, Turing Machines PPT, PDF Sections 8.1, 8.2
5/6, 5/11 More About Turing Machines PPT, PDF Sections 8.3 - 8.6
5/13 Undecidable Problems PPT, PDF Sections 9.1, 9.2
5/13, 5/18, 5/20 More Undecidable Problems PPT, PDF Sections 9.3 - 9.5
5/20 NP-Completeness PPT, PDF Section 10.1
5/25 Satisfiability, Cook's Theorem PPT, PDF Sections 10.2, 10.3
5/27 More NP-Complete Problems PPT, PDF Sections 10.4, 11.1
6/1 PSPACE-Complete Problems PPT, PDF Sections 11.2, 11.3


Course Staff and Contacts

Instructor: Jeffrey D. Ullman
Department of Computer Science,
433 Gates Hall
Email: ullman(..at..)gmail dot com
Office hours: Tu. 11AM - 12:15PM, Fri. 11AM-noon. Also by appointment. (But starting 9:15AM Tuesday 5/4)
 
TAs: Jia Li
Email: lijiali(..at..)stanford.edu
Office hours: Mon. 9AM - Noon.
Location: Gates 240
 
Shrey Gupta
Email: shreyg(..at..)stanford.edu
Office hours (effective from April 9): 2:30 p.m. - 4:00 p.m., Wednesday and Friday
Location: Gates B26-A
 
Rohan Jain
Email: rohanj(..at..)stanford.edu
Office hours (effective from April 5): 2:30 p.m. - 4:00 p.m., Monday and 9:00 a.m. to 10:30 a.m., Friday
Location: Gates B26-A
 
Staff mailing list: cs154-spr0910-staff@lists.stanford.edu

Note:



Hours and Locations

Class: Tuesday-Thursday, 2:15-3:30 p.m.
Gates B01