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:-
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
-
Author: Christos Papadimitriou
Title: Computational Complexity
Publisher: Addison-Wesley
Year/Edition: 1994
Acronym: CP
-
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
|
Sipser Ch. 0, 1.1
|
|
2
|
Sipser 1.1, 1.2
|
|
3
|
Sipser 1.2
|
|
4
|
Sipser 1.3
|
|
5
|
Pumping lemma and non-regular
languages (no slides)
|
Sipser 1.4
|
6
|
||
7
|
Context-free languages: introduction
(no slides)
|
Sipser 2.1
|
|
President's day, no lecture
|
|
8
|
Sipser 2.2
|
|
9
|
Sipser 2.3
|
|
10
|
Examples of non-CFLs;
Context-sensitive languages; the Chomsky hierarchy (no slides)
|
Sipser 2.3
|
11
|
No lecture -- midterm
|
|
12
|
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
|
|
Great article, Thanks for your great information, the content is quiet interesting. I will be waiting for your next post.
ReplyDelete