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 Non-determinism - 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 - Model-Independent Complexity Classes - Deterministic Complexity Classes - Certificates and nondeterminism - Complete Problems. NP-Completeness: 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 NP-Completeness - The Complexity of Approximation – Definitions - Constant-Distance Approximations - Approximation Schemes - Fixed-Ratio 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)