CS 302, Theory of Computation
Purandar Bhaduri, ext: 2360, email: pbhaduri.
Course Contents (Tentative)
Formal Logic: Proof systems for propositional and first-order logic; consistency; completeness; compactness.
Computability: Primitive recursive functions; Godelization; Church's thesis.
Complexity Theory: Review of models of computations, time and space bounded computations. Classes P, NP, polynomial reducibilities, NP-completeness.
CS203 (Discrete Maths), CS301 (Formal Languages and Automata Theory)
There is no prescribed textbook for the course. I will refer to the CSC 438F/2404F notes by Stephen Cook and prepare my own notes for the lectures. You may also refer to the resources cited on the above web page. Other sources will be mentioned as and when used.
You may refer to the following books for additional reading. Please contact the central library for assistance.
1. Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Company (1996?)
2. Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences), M. R. Garey and D. S. Johnson, W. H. Freeman (January 15, 1979)
3. Computational Complexity, Christos H. Papadimitriou, Addison Wesley; 1st edition (November 30, 1993)
4. A Mathematical Introduction to Logic, Herbert Enderton, Harcourt / Academic Press; 2nd edition (December 2000)
5. Logic for Computer Science: Foundations of Automatic Theorem Proving (Harper & Row Computer Science and Technology Series) Jean H. Gallier, John Wiley & Sons; (January 1986). An online version is available here.
Home Assignment Policy
You may discuss the homework problems among yourselves, but the final solution must be in your own words. No credit will be given for identical solutions. No late submission of homework will be accepted.
Assignment #2 (Due 08/03/2005 Tuesday). Exercises 6 (page 44) and 9 (page 46) from the notes. (20 points).
Assignment #3 (Due 17/04/2005 Sunday).