Search This Blog

Saturday, October 1, 2011

Computability and Complexity PPT

Computability and Complexity PPT

Instructor: Sanjit A. Seshia

Course Description

This course will introduce you to three foundational areas of computer science:
  • Automata Theory: What are the basic mathematical models of computation?
  • Computability Theory: What problems can be solved by computers?
  • Complexity Theory: What makes some problems computationally hard and others easy?
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.  

Textbooks

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 
Lec.
Topics (with PDFs of lecture slides, if applicable)
Required Reading
1
Course Overview; Introduction to Finite Automata (PDF2up, PDF )
Sipser Ch. 0, 1.1
2
Finite Automata: DFAs and NFAs ( PDF2up, PDF )
Sipser 1.1, 1.2
3
Equivalence of DFAs and NFAs, closure of regular operations ( PDF2up, PDF )
Sipser 1.2
4
Regular expressions and equivalence with finite automata ( PDF2up, PDF )
Sipser 1.3
5
Pumping lemma and non-regular languages (no slides)
Sipser 1.4
6
Minimization of DFAs; the Myhill-Nerode theorem ( PDF2up, PDF )
7
Context-free languages: introduction (no slides)
Sipser 2.1

President's day, no lecture

8
Pushdown automata; equivalence with CFL ( PDF2up, PDF )
Sipser 2.2
9
PDA-CFL equivalence; Pumping lemma for CFLs ( PDF2up, PDF )
Sipser 2.3
10
Examples of non-CFLs; Context-sensitive languages; the Chomsky hierarchy (no slides)
Sipser 2.3
11
No lecture -- midterm

12
Turing machines; the Church-Turing thesis ( PDF2up, PDF )
Sipser 3.1, 3.3
13
TM examples and TM variants
Sipser 3.2
14
Decidable languages
Sipser 4.1
15
Diagonalization; The Halting Problem
Sipser 4.2
16
Reductions between problems; mapping reducibility
Sipser 5.1, 5.3

Spring break


Spring break

18
Time complexity; The class P
Sipser 7.1, 7.2
19
The classes NP and co-NP; Examples; Polynomial-time reductions
Sipser 7.3, 7.4
20
NP-completeness; examples
Sipser 7.4, 7.5
21
Proof of Cook-Levin theorem, review of reductions
Sipser 7.4
22
PSPACE and NPSPACE; Savitch's theorem
Sipser 8.1, 8.2
23
No lecture -- midterm

24
PSPACE-completeness; The QBF problem
Sipser 8.3
25
The classes L and NL; Log-space reductions; NL-completeness
Sipser 8.4, 8.5
26
The Space Hierarchy Theorem; NP and co-NP; The Time Hierarchy Theorem (start)
Sipser 9.1
27
The Time Hierarchy Theorem (finish); Special topic: Phase transitions in SAT; Wrap-up (PDF)
Sipser 9.1

RRR week


RRR week


Final Exam, 8 - 11 am, in 251 HEARST GYM

 

 

No comments:

Post a Comment