CS172 -- Computability and Complexity (Spring 2005)
University of California at Berkeley
Dept. of Electrical Engineering &
5/9: End-of-the-semester stuff.
5/1: We mean for problem 9.13 to include the change given in the textbook errata. You can search for "problem 9.13" to see the correction.
4/6: Adam will hold extra office hours on Friday, 4/8, 3:30-4:30 in Soda 551 to answer any questions about the upcoming exam (or anything else).
3/14: Adam will be trying the same 1:30-2:30 Wednesday office hours again this week, instead of his old Friday OH.
3/7: Adam's Friday office hours for this week are rescheduled to Wednesday from 1:30-2:30 in 511 Soda. This change might become permanent; we'll see next week if people like this time better.
2/23: From UPE: UPE (CS honor society) and CSUA are holding a LaTeX workshop on Thursday 2/24 6-8pm at 273 Soda. LaTeX is the standard tool for typesetting mathematical documents, and anyone grading your homeworks or papers will thank you for starting to use it, since it tends to make for much more readable solutions.
Please refer to upe.cs.berkeley.edu for more information.
2/8: For PS2, you may assume the result in Problem 2.17a, which says that the set of context-free languages is closed under intersection with regular languages. This might help you give a more concise proof for one of the PS2 problems.
1/31: For problems 1a and 3 of PS1, you'll probably be specifying automata with either pictures or formal descriptions. In either case, we'd like you also to give a brief English description of how your automaton works and why it recognizes the language that you claim it does.
1/26: We've corrected a typo in PS1: the last problem said "indistinguishable" when it should have said "distinguishable."
- There will be no section tomorrow, May 10, and no office hours this week. If you want to meet with either of us this week, you can send us e-mail and we'd be happy to accommodate you, but we expect most of you are more concerned with your earlier finals and class projects now.
- We will have a "review session" next Monday, May 16, at 4 PM in 511 Soda. This isn't going to have a prepared outline like section, so be sure to look over the homework assignments and other material and come with questions, if you decide to attend.
- Brian will hold special extended office hours the week of the exam, Tuesday and Wednesday from 1 to 4 PM in his office, 327 Soda. Adam isn't planning to have any scheduled office hours that week, but, as usual, he can meet with anyone interested by appointment.
||Brian Lucena (e-mail)
Office: 327 Soda
||Adam Chlipala (e-mail)
Office: 579 Soda
||MW 9:30-11:00 AM, 310 Soda Hall
|Office Hours (updated):
M 11:30-12PM, 1-2PM, 327 Soda (Lucena)
M 3-4PM, 551 Soda (Chlipala)
Tu 1-2PM, 327 Soda (Lucena)
W 1:30-2:30PM, 511 Soda (Chlipala)
...or by appointment
(101) Tu 2-3PM, 51 Evans (changed from 71 Evans)
(102) Tu 4-5PM, 136 Barrows
|| Michael Sipser,
Introduction to the Theory of Computation
||ucb.class.cs172 on news.berkeley.edu
Your grade will be determined from the following class components:
45% for weekly problem sets
15% each for two midterm exams
25% for the final exam.
||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
| ||Mean ||Std. dev. ||Median |
|PS11 ||25.1 ||5.1 ||28 |
|PS10 ||29.9 ||6.8 ||30 |
|PS9 ||30.4 ||6.4 ||31 |
|Midterm 2 ||65.3 ||26.6 ||60 |
|PS8 ||31.9 ||8.5 ||34 |
|PS7 ||31.2 ||8.0 ||33 |
|PS6 ||33.2 ||8.8 ||37 |
|PS5 ||28.1 ||8.4 ||28 |
|Midterm 1 ||44.9 ||17.9 ||47 |
|PS4 ||25.5 ||8.6 ||29 |
|PS3 ||30.7 ||7.2 ||32 |
|PS2 ||26.8 ||9.9 ||25 |
|PS1 ||36 ||7.1 ||36.5 |
| ||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 |
|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 |
|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 |
|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 |
|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 |
|17 ||M 3/28 ||P and NP. ||7.2, 7.3 |
|18 ||W 3/30 ||NP-completeness. ||7.4 ||PS7 due |
|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 |
|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 |
|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
- Automata and Languages. In this section we analyze finite
automata (machines with finite memory), pushdown automata (machines
with an infinite LIFO stack) and regular and context-free
languages. These models of computation are thoroughly understood and
there are some elegant equivalences and theorems that can be
shown.However, as we will see, the models in this section are a bit
too restrictive to accurately capture a modern notion of what can and
can’t be done with computers. Still, they are useful models in
their own right.
- Turing Machines and Decidability. Next we study a much
more powerful model of computation, the Turing Machine. This model of
computation has infinite memory, and thus is in most senses more
powerful than a real computer. Despite this, we find that even Turing
Machines have theoretical limitations, leading to some very
fundamental results that are connected with the foundations of
- Complexity Theory. After giving limits on what Turing
Machines can compute, we find that there are still problems that,
though solvable by Turing Machines, are not practically solvable by
computers today. This arises if the time (or space) required is so
large as to be intractable. Complexity theory gives us a handle on
this by analyzing how the time (or space) required by a problem grows
with the size of the input. This leads to the classes P, NP, and
NP-complete in time complexity and L, NL, PSPACE in space
complexity. We also discuss (but do not attempt to solve) the P/NP
conjecture, which is one of the biggest outstanding problems in
mathematics and computer science.
- Advanced Topics. Time permitting we'll cover Probabilistic
Algorithms, Interactive Proof Systems, Cryptography, Applied Aspects
of Complexity, and possibly even a bit on Quantum Computing.