CS 172: Computability and Complexity

Spring 2008

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

Solutions are posted on
bSpace under "Resources".  

Course Schedule (subject to change)

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

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-2008 Sanjit A. Seshia   (except where otherwise stated)
Last modified: Thu Apr 24 10:57:12 PDT 2008