CS 172: Computability and Complexity

Fall 2006

Short-cuts: [   Description   |   Prerequisites   |   Books   |   Grading   |   Homeworks & Exams   |   Schedule   |   Links     |   Course Policies   ]

General Information

Course Description

This course will introduce you to three foundational areas of computer science: Specific topics include: Finite automata, Pushdown automata, Turing machines and RAMs. Undecidable, exponential, and polynomial-time problems. Polynomial-time equivalence of all reasonable models of computation. Nondeterministic Turing machines. Theory of NP-completeness: Cook's theorem, NP-completeness of basic problems. Selected topics in language theory, complexity and randomness.

Credits: 4 units


An upper division algorithms course --- CS 170 (or equivalent), and a basic discrete mathematics course --- Math 55 or CS 70. Anyone lacking the above background will not be admitted except under special circumstances, and must meet the instructor in the first week.


The required textbook for this course is the following:
Author: Michael Sipser
Title: Introduction to the Theory of Computation
Publisher: Course Technology (Thomson)
Year/Edition: 2nd edition, 2005
Acronym: Sipser

The following books are recommended for further reading:

  1. Authors: John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman
    Title: Introduction to Automata Theory, Languages, and Computation
    Publisher: Addison-Wesley
    Year/Edition: 2nd or 3rd edition
    Acronym: HMU
  2. Author: Christos Papadimitriou
    Title: Computational Complexity
    Publisher: Addison-Wesley
    Year/Edition: 1994
    Acronym: CP
  3. Authors: Michael Garey and David Johnson
    Title: Computers and Intractability
    Publisher: Freeman
    Year/Edition: 1979
    Acronym: GJ

Copies of all of the above books are on reserve at the Engineering library.


Here are the
EECS guidelines for grading in undergraduate courses.

Homeworks & Exams


Course Schedule (subject to change)

Lec. Date Topics (with PDFs of lecture slides) Required Reading Homeworks & Milestones
1 8/28 Course Overview; Introduction to Finite Automata (PDF2up) Sipser Ch. 0, 1.1  
2 8/30 Finite Automata: DFAs and NFAs ( PDF2up, PDF ) Sipser 1.1, 1.2 HW 1 out
  9/4 No lecture, Labor Day    
3 9/6 Equivalence of DFAs and NFAs, closure of regular operations ( PDF2up, PDF ) Sipser 1.2 HW 1 due
  9/11 Class cancelled -- make up class 2-3 pm on 9/15, in 310 Soda   HW 2 out
4 9/13 Regular expressions and equivalence with finite automata ( PDF2up, PDF ) Sipser 1.3  
5 9/15 Pumping lemma and non-regular languages (no slides) Sipser 1.4  
6 9/18 Minimization of DFAs; the Myhill-Nerode theorem ( PDF2up, PDF ) Handout HW 2 due; HW 3 out
7 9/20 Context-free languages: introduction (no slides) Sipser 2.1  
8 9/25 Pushdown automata; equivalence with CFL ( PDF2up, PDF ) Sipser 2.2 HW 3 due; HW 4 out
9 9/27 PDA-CFL equivalence; Pumping lemma for CFLs ( PDF2up, PDF ) Sipser 2.3  
10 10/2 Examples of non-CFLs; Context-sensitive languages; the Chomsky hierarchy (no slides) Sipser 2.3 HW 4 due
11 10/4 No lecture -- midterm   Midterm 1
12 10/9 Turing machines; the Church-Turing thesis ( PDF2up, PDF ) Sipser 3.1, 3.3  
13 10/11 TM examples and TM variants (no slides) Sipser 3.2 HW 5 out
14 10/16 Decidable languages (no slides) Sipser 4.1  
15 10/18 Diagonalization; The Halting Problem (no slides) Sipser 4.2 HW 5 due; HW 6 out
16 10/23 Reductions between problems; mapping reducibility (no slides) Sipser 5.1, 5.3  
17 10/25 The Post Correspondence Problem ( PPT ) Sipser 5.1, 5.2 HW 6 due; HW 7 out
18 10/30 Decidability of Logical Theories; Goedel's Incompleteness Theorem (no slides) Sipser 6.2  
19 11/1 Time complexity; The class P (no slides) Sipser 7.1, 7.2 HW 7 due
20 11/6 The classes NP and co-NP; Examples; Polynomial-time reductions (no slides) Sipser 7.3, 7.4 HW 8 out
21 11/8 NP-completeness; examples (no slides) Sipser 7.4, 7.5  
22 11/13 Proof of Cook-Levin theorem, review of reductions (no slides) Sipser 7.4 HW 8 due
23 11/15 No lecture -- midterm   Midterm 2
24 11/20 PSPACE and NPSPACE; Savitch's theorem; PSPACE-completeness (no slides) Sipser 8.1, 8.2, 8.3  
25 11/22 The QBF problem; The classes L and NL (no slides) Sipser 8.3, 8.4 HW 9 out
26 11/27 Log-space reductions; NL-completeness (no slides) Sipser 8.4, 8.5  
27 11/29 The Space Hierarchy Theorem; NP and co-NP (no slides) Sipser 9.1 HW 10 out; HW 9 due on 12/1
28 12/4 The Time Hierarchy Theorem; Probabilistic complexity classes (Sipser 10.2, optional) Sipser 9.1  
29 12/6 Special topic: Phase transitions in SAT (PDF); Course wrap-up   HW 10 due on 12/8
  12/15 Final Exam, 5 - 8 pm, 70 Evans    

Links to Misc. Information

Optional Reading:

Course Policies

Collaboration: Collaboration on homeworks with other students in this class is encouraged. You may work in groups of at most three people; however, you must always write up the solutions on your own and indicate the names of those you worked with. Similarly, you may use references to help solve homework problems, but you must write up the solution on your own and cite your sources. In particular, help must not be sought from students who have taken the course in previous years, and you may not review homework solutions from previous years. Your acknowledgment of collaboration will not be used to penalize you, nor will it affect your grade in any way. It is intended only for your own protection.

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.

Copyright 2006 Sanjit A. Seshia   (except where otherwise stated)
Last modified: Wed Nov 22 07:37:00 PST 2006