Related Links
Ref Books

Course Contents

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.

Course Synopsis

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

Course Learning Outcomes

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.

Course Material

View Now

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