To define, study various computational models and programming constructs
To classify computational problems in terms of their inherent complexity
To understand relative power and limitations of the above models and constructs
To apply this understanding to address problems arising in other parts of computer science, mathematics and other related fields

1. Numbers and their Representation  Problems, Instances, and Solutions  Asymptotic Notation – Graphs  Alphabets, Strings, and Languages  Functions and Infinite Sets  Pairing Functions  Cantor's Proof: the Technique of Diagonalization  Implications for Computability
2. Finite automata and Regular Languages: States and Automata  Finite Automata as Language Acceptors  Determinism and Nondeterminism  Checking vs. Computing  Properties of Finite Automata  Equivalence of Finite Automata Epsilon Transitions  Regular Expressions and Finite Automata  Reviewing the Construction of Regular Expressions from Finite Automata.
3. Universal Models of Computation  Encoding Instances  Choosing a Model of Computation  Issues of Computability  The Turing Machine  Multitape Turing Machines  The Register Machine  Translation Between Models  Computability Theory  Primitive Recursive Functions Defining Primitive Recursive Functions  Partial Recursive Functions  Rice's Theorem and the Recursion Theorem  Degrees of Unsolvability
4. Complexity Theory: Classes of Complexity  Hierarchy Theorems  ModelIndependent Complexity Classes  Deterministic Complexity Classes  Certificates and nondeterminism  Complete Problems. NPCompleteness: Cook's Theorem  Space Completeness  Polynomial Space  Polylogarithmic Space  Provably Intractable Problems
5. Complexity Theory in Practice: Circumscribing Hard Problems  Restrictions of Hard Problems  Promise Problems  Strong NPCompleteness  The Complexity of Approximation – Definitions  ConstantDistance Approximations  Approximation Schemes  FixedRatio Approximations and the Class OptNP  The Power of Randomization. 
1. The Theory of Computation – Bernard Moret, AW, (1998)
2. Introduction to Automata Theory, Languages and Computation – John E Hopcroft, AW, (2001)
3. Theory of Computation – Formal Languages, Automata and Complexity, AW, J. Glenn Brookshear (1989)
4. Models of Computation – Exploring the power of Computing – John Savage (1998)
