University of California at Berkeley
Dept. of Electrical Engineering &
Computer Science
Instructor:  Brian Lucena (email) Office: 327 Soda 

GSI:  Adam Chlipala (email) Office: 579 Soda 

Lectures:  MW 9:3011: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  Nonregular languages; the pumping lemma for regular languages. Contextfree languages.  1.4, 2.1  PS1 out 
4  M 1/31  More contextfree languages. The pumping lemma for contextfree languages.  2.1, 2.3  
5  W 2/2  More pumping lemma for contextfree 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  Nondeterministic 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  NPcompleteness.  7.4  PS7 due PS8 out 
19  M 4/4  More NPcompleteness.  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  PSPACEcompleteness.  8.3  PS9 out 
23  M 4/18  Games. More PSPACEcompleteness. 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 wrapup. 
This course discusses the power and limitations of computing devices from a theoretical viewpoint. It can roughly be divided into four sections.