Credits: 4 units
The following books are recommended for further reading:
Copies of all of the above books are on reserve at the Engineering library.
| Lec. | Date | Topics (with PDFs of lecture slides) | Required Reading | Homeworks & Milestones |
|---|---|---|---|---|
| 1 | 8/28 | Course Overview; Introduction to Finite Automata (PDF2up) | Sipser Ch. 0, 1.1 | |
| 2 | 8/30 | Finite Automata: DFAs and NFAs ( PDF2up, PDF ) | Sipser 1.1, 1.2 | HW 1 out |
| 9/4 | No lecture, Labor Day | |||
| 3 | 9/6 | Equivalence of DFAs and NFAs, closure of regular operations ( PDF2up, PDF ) | Sipser 1.2 | HW 1 due |
| 9/11 | Class cancelled -- make up class 2-3 pm on 9/15, in 310 Soda | HW 2 out | ||
| 4 | 9/13 | Regular expressions and equivalence with finite automata ( PDF2up, PDF ) | Sipser 1.3 | |
| 5 | 9/15 | Pumping lemma and non-regular languages (no slides) | Sipser 1.4 | |
| 6 | 9/18 | Minimization of DFAs; the Myhill-Nerode theorem ( PDF2up, PDF ) | Handout | HW 2 due; HW 3 out |
| 7 | 9/20 | Context-free languages: introduction (no slides) | Sipser 2.1 | |
| 8 | 9/25 | Pushdown automata; equivalence with CFL ( PDF2up, PDF ) | Sipser 2.2 | HW 3 due; HW 4 out |
| 9 | 9/27 | PDA-CFL equivalence; Pumping lemma for CFLs ( PDF2up, PDF ) | Sipser 2.3 | |
| 10 | 10/2 | Examples of non-CFLs; Context-sensitive languages; the Chomsky hierarchy (no slides) | Sipser 2.3 | HW 4 due |
| 11 | 10/4 | No lecture -- midterm | Midterm 1 | |
| 12 | 10/9 | Turing machines; the Church-Turing thesis ( PDF2up, PDF ) | Sipser 3.1, 3.3 | |
| 13 | 10/11 | TM examples and TM variants (no slides) | Sipser 3.2 | HW 5 out |
| 14 | 10/16 | Decidable languages (no slides) | Sipser 4.1 | |
| 15 | 10/18 | Diagonalization; The Halting Problem (no slides) | Sipser 4.2 | HW 5 due; HW 6 out |
| 16 | 10/23 | Reductions between problems; mapping reducibility (no slides) | Sipser 5.1, 5.3 | |
| 17 | 10/25 | The Post Correspondence Problem ( PPT ) | Sipser 5.1, 5.2 | HW 6 due; HW 7 out |
| 18 | 10/30 | Decidability of Logical Theories; Goedel's Incompleteness Theorem (no slides) | Sipser 6.2 | |
| 19 | 11/1 | Time complexity; The class P (no slides) | Sipser 7.1, 7.2 | HW 7 due |
| 20 | 11/6 | The classes NP and co-NP; Examples; Polynomial-time reductions (no slides) | Sipser 7.3, 7.4 | HW 8 out |
| 21 | 11/8 | NP-completeness; examples (no slides) | Sipser 7.4, 7.5 | |
| 22 | 11/13 | Proof of Cook-Levin theorem, review of reductions (no slides) | Sipser 7.4 | HW 8 due |
| 23 | 11/15 | No lecture -- midterm | Midterm 2 | |
| 24 | 11/20 | PSPACE and NPSPACE; Savitch's theorem; PSPACE-completeness (no slides) | Sipser 8.1, 8.2, 8.3 | |
| 25 | 11/22 | The QBF problem; The classes L and NL (no slides) | Sipser 8.3, 8.4 | HW 9 out |
| 26 | 11/27 | Log-space reductions; NL-completeness (no slides) | Sipser 8.4, 8.5 | |
| 27 | 11/29 | The Space Hierarchy Theorem; NP and co-NP (no slides) | Sipser 9.1 | HW 10 out; HW 9 due on 12/1 |
| 28 | 12/4 | The Time Hierarchy Theorem; Probabilistic complexity classes (Sipser 10.2, optional) | Sipser 9.1 | |
| 29 | 12/6 | Special topic: Phase transitions in SAT (PDF); Course wrap-up | HW 10 due on 12/8 | |
| 12/15 | Final Exam, 5 - 8 pm, 70 Evans |
Academic Dishonesty: Copying solutions or code, in whole or in part, from other students or any other source without acknowledgment constitutes cheating. Any student found to be cheating in this class risks automatically receiving an F grade and referral to the Office of Student Conduct. The Department's Policy on Academic Dishonesty is available at http://www.eecs.berkeley.edu/Policies/acad.dis.shtml .
Special Requests: It is your responsibility to see the instructor in a timely fashion for accommodation of religious beliefs, disabilities, and other special circumstances.
Feedback: The course staff always welcome your suggestions and feedback on what we could do better. Please feel free to contact us in person or via e-mail. If you would like to send anonymous comments or criticisms, you can use an anonymous remailer, like this one, to send us e-mail without revealing your identity.
