School of Engineering and Technology, (SET)
 
AT70.03 : Theory of Computing  3(3-0)
 
Course objectives:

To provide an exposure to the theory of formal languages, automata and complexity theory.
 
Learning Outcomes:

Finite Automata and Regular Expressions. Properties of Regular Sets. Context-Free Grammars. Pushdown Automata. Properties of Context-Free Languages. Turing Machines. Undecidability. Computational Complexity Theory. Intractable Problems.
 
Pre-requisite(s):

None
 
Course Outline:
I.       Finite Automata and Regular Expressions
1.    Finite State Systems
2.    Non-deterministic Finite Automata
3.    Regular Expressions

II.      Properties of Regular Sets
1.    The Pumping Lemma for Regular Sets
2.    Closure Properties of Regular Sets
3.    Decision Algorithms for Regular Sets

III.     Context-Free Grammars, Pushdown Automata
1.    Derivation Trees
2.    Simplication of Context-Free Grammars
3.    Normal Forms
4.    Pushdown Automata
5.    Properties of Context-Free Languages: The Pumping Lemma for CFL's, Closure Properties of CFL's, Decision Algorithms for CFL's

IV.     Turing Machines
1.     Computable Languages and Functions
2.     Church's Hypothesis

V.      Undecidability
1.     Properties of Recursive and Recursively Enumerable Languages
2.     Universal Turing Machines and Undecidable Problem
3.     Recursive Function Theory

VI.     The Chonsky Hierarchy

VII.   Computational Complexity Theory: Tractability and Intractability
1.     Deterministic Turing Machines and the Class P
2.     Nondeterministic Turing Machines and the Class NP
3.     Relationship between P and NP
4.     Polynomial Transformation and NP-Completeness
5.     Cook’s Theorem
6.     NP-Complete Problems
7.     NP-Hardness


 
 
Learning Resources:

Textbook:
H.R. Lewis, C.H. Papadimitriou:
        Element of the Theory of Computation, Prentice Hall, 2nd Edition, 1998.
 
Reference Books:
C. Calude:
        Theories of Computational Complexity, North Holland, 1988.

M. Chandrasekaran, and K.L.P. Mishra:
        Theory of Computer Science: Automata, Language and Computation, Prentice Hall, 1995.

J.E. Hopcroft, J.D. Ullman:
        Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Massachusetts, 1979.

M. Sipser:
        Introduction to the Theory of Computation, Pws Pub Co, USA, 1996.

C.H. Smith:
        A Recursive Introduction to the Theory of Computation, Springer Verlag, 1994.

R.G. Taylor:
        Model of Computation and Formal Languages, Oxford University Press, 1997.

M.R. Garey and D. S. Johnson:
        Computer and Intractability, W.H. Freeman and Company, New York, 1979.
 
 
 
 
Evaluation Scheme:
The final grade will be computed from the following constituent parts:

Mid-semester exam       - (30%)
Final exam                     - (70%)

Open-book examination is used for both mid-semesterand final exam.
 
Instructor(s):
SECTION NAME