CS 603: Fundamentals of Theoretical Computer Science
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:
- Raynold M. Smullyan.First-Order Logic, Springer-Verlag, 1968.
- J. E. Hopcroft and J. Ullman.Introduction to Antomata Theory, Languages of Computations, Addison Wesley, 1979. (Indian edition available from Narosa.)
- J. L. Balcazar, J. Diaz and J. Gabarro.Structural Complexity I, Springer- Verlag, 1988.
- M. R. Garey and D. S. Johnson.Computers & Intractability, W. H. Freeman & Co., San Farnisco, 1979.