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, if applicable) | Required Reading | Homeworks & Milestones |
|---|---|---|---|---|
| 1 | 1/20 | Course Overview; Introduction to Finite Automata (PDF2up, PDF ) | Sipser Ch. 0, 1.1 | |
| 2 | 1/25 | Finite Automata: DFAs and NFAs ( PDF2up, PDF ) | Sipser 1.1, 1.2 | HW 1 out |
| 3 | 1/27 | Equivalence of DFAs and NFAs, closure of regular operations ( PDF2up, PDF ) | Sipser 1.2 | |
| 4 | 2/1 | Regular expressions and equivalence with finite automata ( PDF2up, PDF ) | Sipser 1.3 | HW 1 due; HW 2 out |
| 5 | 2/3 | Pumping lemma and non-regular languages (no slides) | Sipser 1.4 | |
| 6 | 2/8 | Minimization of DFAs; the Myhill-Nerode theorem ( PDF2up, PDF ) | Handout | HW 2 due; HW 3 out |
| 7 | 2/10 | Context-free languages: introduction (no slides) | Sipser 2.1 | |
| 2/15 | President's day, no lecture | HW 3 due Tue 2/16 in drop box by 5 pm | ||
| 8 | 2/17 | Pushdown automata; equivalence with CFL ( PDF2up, PDF ) | Sipser 2.2 | HW 4 out |
| 9 | 2/22 | PDA-CFL equivalence; Pumping lemma for CFLs ( PDF2up, PDF ) | Sipser 2.3 | |
| 10 | 2/24 | Examples of non-CFLs; Context-sensitive languages; the Chomsky hierarchy (no slides) | Sipser 2.3 | HW 4 due |
| 11 | 3/1 | No lecture -- midterm | Midterm 1 | |
| 12 | 3/3 | Turing machines; the Church-Turing thesis ( PDF2up, PDF ) | Sipser 3.1, 3.3 | HW 5 out Mar 4 |
| 13 | 3/8 | TM examples and TM variants | Sipser 3.2 | |
| 14 | 3/10 | Decidable languages | Sipser 4.1 | HW 5 due & HW 6 out Mar 11 |
| 15 | 3/15 | Diagonalization; The Halting Problem | Sipser 4.2 | |
| 16 | 3/17 | Reductions between problems; mapping reducibility | Sipser 5.1, 5.3 | HW 6 due |
| 3/22 | Spring break | |||
| 3/24 | Spring break | |||
| 18 | 3/29 | Time complexity; The class P | Sipser 7.1, 7.2 | HW 7 out |
| 19 | 3/31 | The classes NP and co-NP; Examples; Polynomial-time reductions | Sipser 7.3, 7.4 | |
| 20 | 4/5 | NP-completeness; examples | Sipser 7.4, 7.5 | HW 7 due; HW 8 out |
| 21 | 4/7 | Proof of Cook-Levin theorem, review of reductions | Sipser 7.4 | |
| 22 | 4/12 | PSPACE and NPSPACE; Savitch's theorem | Sipser 8.1, 8.2 | HW 8 due |
| 23 | 4/14 | No lecture -- midterm | Midterm 2 | |
| 24 | 4/19 | PSPACE-completeness; The QBF problem | Sipser 8.3 | |
| 25 | 4/21 | The classes L and NL; Log-space reductions; NL-completeness | Sipser 8.4, 8.5 | HW 9 out |
| 26 | 4/26 | The Space Hierarchy Theorem; NP and co-NP; The Time Hierarchy Theorem (start) | Sipser 9.1 | |
| 27 | 4/28 | The Time Hierarchy Theorem (finish); Special topic: Phase transitions in SAT; Wrap-up (PDF) | Sipser 9.1 | HW 10 out; HW 9 due |
| 5/3 | RRR week | |||
| 5/5 | RRR week | HW 10 due | ||
| 5/11 | Final Exam, 8 - 11 am, in 251 HEARST GYM |
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.