CS 302, Theory of Computation

Spring 2005-2006

Instructor 

Purandar Bhaduri, ext: 2360, email: pbhaduri.

TA

Pravakar Garnayak, email: pravakar

Office Hours

     Mon, Wed, Fri: 3:00 – 4:00 PM (or by appointment)

Course Contents (Tentative)

Formal Logic: Proof systems for propositional and first-order logic; consistency; completeness; compactness.

Primitive and Partial recursive functions; Computability; 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.      A Mathematical Introduction to Logic, Herbert Enderton, Harcourt / Academic Press; 2nd edition (December 2000)

2.      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.

3.      Introduction to the Theory of Computation, Michael Sipser, PWS Publishing Company (1996)

4.      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)

5.      Computational Complexity, Christos H. Papadimitriou, Addison Wesley; 1st edition (November 30, 1993)

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.

 back to homepage