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