| Announcements |
| Course Information |
| Exams from This Course |
| Homework Assignments |
| Date Due | Assignment | Solutions |
|---|---|---|
| 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 |
| Date | Subject | Slides | Readings |
|---|---|---|---|
| 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 |
| Hours and Locations |
| Class: | Tuesday-Thursday, 2:15-3:30 p.m. |
| Gates B01 | |