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 | |