Hi Guest, 28 February 2021 Sunday IST

About CUSAT | About Department | Alumni | Sitemap | Disclaimer  

  Home > Academic/Programmes > Programme Structure > CIS (2009)

Core/Elective: Core Semester: 1 Credits: 4

Course Description

Theory of computation is a branch of mathematics that studies the types of tasks that are theoretically possible with computing machines. It is also concerned with the relative difficulty and complexity of these tasks. Mathematical models for computers such as Turing machines and finite automata are essential tools.

Course Objectives

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

Course Content

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)

Copyright © 2009-21 Department of Computer Science,CUSAT
Design,Hosted and Maintained by Department of Computer Science
Cochin University of Science & Technology
Cochin-682022, Kerala, India
E-mail: csdir@cusat.ac.in
Phone: +91-484-2577126
Fax: +91-484-2576368