CS172 -- Computability and Complexity (Spring 2005)

University of California at Berkeley
Dept. of Electrical Engineering & Computer Science


  • 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."

  • 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):
  • 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
    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:
  • 45% for weekly problem sets
  • 15% each for two midterm exams
  • 25% for the final exam.
    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

    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
    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.

    Course Description

    This course discusses the power and limitations of computing devices from a theoretical viewpoint. It can roughly be divided into four sections.

    1. 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.
    2. 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 mathematics.
    3. 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.
    4. 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.