The theory of computation is concerned with the theoretical limits of computability. Several mathematical models of computation have been formulated independently and under any such computational model, the existence of well-defined but unsolvable problems can be formally shown. This course examines important theorems and proofs, establishes a number of interesting assertions in order to expose the techniques used in the area of theory of computation. This course makes significant use of mathematical structures, abstractions, definitions, theorems, proofs, lemmas, corollaries, logical reasoning, inductive proofs, and the like.

To discuss and understand theoretical concepts for the computational complexity of algorithmic problems

Students will be able to : • Define and describe formal models of computation, such as finite automata, pushdown automata, and Turing machines. • Give examples of languages and computational problems appropriate for different models of computation. • Understand statements regarding formal models of computation. • Use basic concepts and explain implications of modern complexity theoretic approaches.

Book Title : Introduction to the Theory of Computation

Author : Michael Sipser

Edition : First Edition

Publisher : PWS Publishing Company

Book Title : Computational Complexity

Author : Christos Papadimitriou

Edition :

Publisher : Addison-Wesley

Book Title : Introduction to Automata Theory, Languages, and Computation

Author : John Hopcroft and Jeffrey Ullman

Edition : (or the second edition)

Publisher : Addison-Wesley

Book Title : Formal models and Computability, in Handbook of Computer Science

Author : Tao Jiang, Ming Li, and Bala Ravikumar

Edition :

Publisher : CRC Press

Book Title : Introduction to Algorithms

Author : T.H. Cormen, et al

Edition :

Publisher : MIT Press and McGraw-Hill Book Co.

Book Title : An Introduction to Formal Languages and Automata

Author : Peter Linz

Edition :

Publisher :

No Information Yet