| Course Outline | General Information | Study Material | Lectures (classwise) | Useful Links |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to study complexity classes and their interrelations.
We will try to stick to the basic course outline as given in this page, but may deviate a bit.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms, Automata and Finite Languages, and Discrete Structures courses.
| Class Timings: | Tuesday 09:30-11:15, Thursday 09:30-11:15 ACM Unit Seminar Room (Main Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| Books |
(1) Computational Complexity: A Modern Approach Sanjeev Arora and Boaz Barak Cambridge University Press A pre-publication draft is available here. We would follow this as our text book. (2) Introduction to the Theory of Computation Michael Sipser Thomson (Brooks/Cole), International Student Edition (3) M. R. Garey and D. S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman (4) Approximation Algorithms V. V. Vazirani Springer (5) Approximation Algorithms for NP-Hard problems D. S. Hochbaum (edited) Thomson (6) Algorithm Design Jon Kleinberg and Eva Tardos Pearson Education (7) Computational Complexity: A Conceptual Perspective Oded Goldreich Cambridge University Press Drafts and several on-line versions are available at Oded Goldreich's home page. (8) Notes by Jaikumar Radhakrishnan available at Jaikumar Radhakrishnan's home page. (9) Notes by Luca Trevisan available at Luca Trevisan's home page. |
| LECTURE DATES | TOPICS | LECTURE SLIDES/NOTES (pdf) | BOOKS |
| Lecture 1 (14-01-10) |
Sizes of Sets, Turing Machines | - | (1), (2) |
| Lecture 2 (19-01-10) |
Turing recognizability and decidability; Halting Problem |
- | (1), (2) |
| Lecture 3 (21-01-10) |
NP, NP-completeness, Reductions, Decision vs Search Problems | Lecture 3 | (1), (2), (6) |
| Lecture 4 (04-02-10) |
NP and beyond | Lecture 4 | (1) |
| Lecture 5 (09-02-10) |
coNP, EXP, NEXP | Lecture 5 | (1) |
| Lecture 6 (11-03-10) |
Cook Levin's Theorem | Lecture 6 | (2), (1) |
| Lecture 7 (16-03-10) |
Diagonalization | Lecture 7 | (1) |
| Lecture 8 (18-03-10) |
Space Complexity | Lecture 8 | (1), (2) |
| Lecture 9 (23-03-10) |
Space Complexity | Lecture 9 | (1), (2) |
| Lecture 10 (27-03-10) |
Space Complexity | Lecture 10 | (1), (2) |
| Lecture 11 (30-03-10) |
Polynomial Hierarchy I | Lecture 11 | (1), (2) |
| Lecture 12 (06-04-10) |
Polynomial Hierarchy II | Lecture 12 | (1), (2) |
| Lecture 13 (13-04-10) |
Oracle Turing Machines | Lecture 13 | (1), (2) |
| Lecture 14 (17-04-10) |
Boolean Circuits I | Lecture 14 | (1), (2) |
| Lecture 15 (20-04-10) |
Boolean Circuits II | Lecture 15 | (1), (2), (7), (8) |
| Lecture 16 (22-04-10) |
Randomized Computation | Lecture 16 | (1) |
| Lecture 17 (23-04-10) |
Interactive Proofs | Lecture 17 | (1) |
| Lecture 18 (26-04-10) |
PCP Theorem and Hardness of Approximation I | Lecture 18 | (1), (4), (9) |
| Lecture 19 (28-04-10) |
PCP Theorem and Hardness of Approximation II | Lecture 19 | (1), (4), (9) |