CS 302,
Theory of Computation
Spring 2004-2005Instructor 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. Prerequisites CS203 (Discrete Maths), CS301 (Formal Languages and Automata Theory) Textbook 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. Reference Books 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. Handouts 1. Gentzen's Proof System PK for Propositional Logic 2. Gentzen’s Proof System LK for First Order Logic 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. Home Assignments Assignment #1 (Due 25/01/2005 Tuesday). You may like to try the alternative. 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). |