COURSE OBJECTIVES
This course will introduce Learners about three foundational areas of computer science namely the basic mathematical models of computation, problems that can be solved by computers and problems that are computationally hard. It also introduces basic computation models, their properties and the necessary mathematical techniques to prove more advanced attributes of these models. The learners will be able to express computer science problems as mathematical statements and formulate proofs.
COURSE DURATION: 8 Weeks
COURSE OUTCOMES:
Upon successful completion of this course, learners will be able to
Interpret the mathematical foundations of computation including automata theory; the theory of formal languages and grammars; the notions of algorithm, decidability, complexity, and computability
Construct the abstract machines including finite automata, pushdown automata, and Turing machines from their associated languages and grammar
Make use of pumping lemma to show that a language is not regular / not context-free
Construct the grammar for any given finite automata, pushdown automata or Turing machines
Outline the characteristics of P, NP and NP Complete problems
Solve computational problems regarding their computability and complexity and prove the basic results of the theory of computation
COURSE CONTENTS:
AUTOMATA FUNDAMENTALS
Week 1: Formal Proofs-Finite Automata – deterministic and nondeterministic, regular operations
REGULAR EXPRESSIONS AND LANGUAGES
Week 2: Regular Expression, Equivalence of DFA, NFA and REs, closure properties
Week 3: Non regular languages and pumping lemma, DFA Minimization,
CONTEXT FREE GRAMMAR AND LANGUAGES
Week 4: CFGs, Chomsky Normal Form, Non CFLs and pumping lemma for CFLs
Week 5: PDAs, Equivalence of PDA and CFG, Properties of CFLs, DCFLs
PROPERTIES OF CONTEXT FREE LANGUAGES
Week 6: Turing Machines and its variants- Programming Techniques for TM UNDECIDABILITY
Week 7: Closure properties of decidable languages, Undecidability, Reductions, Post Correspondence Problem
Week 8: Rice's Theorem, introduction to complexity theory, The Class P and NP
COURSE INSTRUCTORS:
- Dr.R.Leena Sri
- Dr.M.K.Kavitha Devi
- Dr.K.Sundharakantham
