University of California at Berkeley
Dept. of Electrical Engineering &
Computer Science
Instructor: | Brian Lucena (e-mail) Office: 327 Soda |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
GSI: | Adam Chlipala (e-mail) Office: 579 Soda |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Lectures: | MW 9:30-11:00 AM, 310 Soda Hall | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Office Hours (updated): |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Section: |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Textbook: | Michael Sipser, Introduction to the Theory of Computation | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Newsgroup: | ucb.class.cs172 on news.berkeley.edu | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Grading: |
Your grade will be determined from the following class components:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Problem Sets: | The weekly problems sets for this class comprise a large
percentage of the total grade. Discussing approaches to the problems
and high level ideas is strongly encouraged. However, detailed
explanations of how exactly to do a problem are not permitted. If you
are stuck on a problem feel free to contact the course staff via email
or at office hours.
Problem sets with class score statistics
|
Day | Topics | Book sections | ||
1 | W 1/19 | Class overview. Regular languages and deterministic finite automata (DFAs). | 1.1 | |
2 | M 1/24 | Nondeterministic finite automata (NFAs). | 1.2 | |
3 | W 1/26 | Non-regular languages; the pumping lemma for regular languages. Context-free languages. | 1.4, 2.1 | PS1 out |
4 | M 1/31 | More context-free languages. The pumping lemma for context-free languages. | 2.1, 2.3 | |
5 | W 2/2 | More pumping lemma for context-free languages. Pushdown automata. CFLs are representable with PDAs. | 2.3, 2.2 | PS1 due PS2 out |
6 | M 2/7 | PDAs describe CFLs. Turing machines. | 2.2, 3.1 | |
7 | W 2/9 | More Turing machines. | 3.1, 3.2 | PS2 due PS3 out |
8 | M 2/14 | Non-deterministic Turing machines. Algorithms. Review of diagonalization | 3.2, 3.3, 4.2 | |
9 | W 2/16 | Decidability | 4.1, 4.2 | PS3 due PS4 out |
10 | W 2/23 | Reductions for decidability. | 5.1, 5.3 | PS4 due |
11 | M 2/28 | Midterm exam 1 (open book, open notes) | ||
12 | W 3/2 | More reductions. Reductions via computation histories. | 5.1, 5.3 | PS5 out |
13 | M 3/7 | More reductions via computation histories. Post correspondence problem. | 5.1, 5.2 | |
14 | W 3/9 | More Post correspondence problem. The recusion theorem. | 5.2, 6.1 | PS5 due PS6 out |
15 | M 3/14 | Turing reducibility. Descriptive complexity. | 6.3, 6.4 | |
16 | W 3/16 | Introduction to time complexity. | 7.1, 7.2, 7.3 | PS6 due PS7 out |
17 | M 3/28 | P and NP. | 7.2, 7.3 | |
18 | W 3/30 | NP-completeness. | 7.4 | PS7 due PS8 out |
19 | M 4/4 | More NP-completeness. | 7.4, 7.5 | |
20 | W 4/6 | Savitch's Theorem and PSPACE. | 8.1, 8.2 | PS8 due |
21 | M 4/11 | Midterm exam 2 | ||
22 | W 4/13 | PSPACE-completeness. | 8.3 | PS9 out |
23 | M 4/18 | Games. More PSPACE-completeness. L and NL. | 8.3, 8.4 | |
24 | W 4/20 | More L and NL. | 8.4, 8.5, 8.6 | PS9 due PS10 out |
25 | M 4/25 | NL=coNL. The space hierarchy theorem. | 8.6, 9.1 | |
26 | W 4/27 | The time hierarchy theorem. Approximation algorithms. | 9.1, 10.1 | PS10 due PS11 out |
27 | M 5/2 | More approximation algorithms. Probabilistic algorithms. | 10.1, 10.2 | |
28 | W 5/4 | More probablistic primality checking. Cryptography. | 10.2, 10.6 | PS11 due |
29 | M 5/9 | Overview and wrap-up. |
This course discusses the power and limitations of computing devices from a theoretical viewpoint. It can roughly be divided into four sections.