CS 603: Fundamentals of Theoretical Computer Science

Course Contents:

Logic: basics of propositional and first order logic, completeness & compactness results. Some applications to computer science. (E.g., theorem proving, logic programming).

Theory of computation: Church's thesis, undecidability.

Computational complexity: time & tape bounds, time & tape bounded simulations, notion of complexity classes, classes P & NP, NP-completeness, some natural NP-complete problems.

Books and References:

1. Raynold M. Smullyan.First-Order Logic, Springer-Verlag, 1968.
2. J. E. Hopcroft and J. Ullman.Introduction to Antomata Theory, Languages of Computations, Addison Wesley, 1979. (Indian edition available from Narosa.)
3. J. L. Balcazar, J. Diaz and J. Gabarro.Structural Complexity I, Springer- Verlag, 1988.
4. M. R. Garey and D. S. Johnson.Computers & Intractability, W. H. Freeman & Co., San Farnisco, 1979.