Basic Information


Course Objectives:

To introduce students the basic concepts in theoretical computer science, and the formal relationships among machines, languages and grammars and computational problems.

Syllabus:

Following is the syllabus for the course. This is an almost lossless rephrasing of the syllabus from department website, except for the word "optional". It is very likely that we will not cover the optional topics. But we will reach a point where they are just a few reads away, so that interested readers can go after the extra references provided in the class.
  • Finite Automata & Regular Languages: Introduction to automata theory, languages and computational problems. Finite state automata, Regular Languages. Deterministic and Non-deterministic finite automata, Subset construction. Regular Expressions, Pattern Matching
  • Context Free Languages and Push Down Automata : Grammars - Production systems - Chomskian hierarchy - Context free grammars - Normal forms - uvwxy theorem - Parikh mapping - Self embedding property - subfamilies of CFL - Derivation trees and ambiguity. Pushdown automata - Acceptance by empty store and final state - Equivalence between push-down automata and context-free grammars - Closure properties of CFL - Deterministic push-down automata - Parsing - CYK algorithm
    Optional Topics : Deterministic bottom-up and top-down parsing - LR(k) and LL(k) grammars - Complexity of parsing algorithms, Lex and Yacc, Compiler tools.
  • Turing machines & Computability - Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Universal Turing machine - Recursively enumerable sets and recursive sets - Context sensitive languages and linear bounded automata. Decidability; Post's correspondence problem; Rice's theorem; decidability of membership, emptiness and equivalence problems of languages.
    Optional Topics : Primitive recursive function; primitive recursive predicates; bounded and unbounded minimization; ยต recursive functions - Godel numbering - equivalence to Turing computable functions.
  • Basic Complexity Theory : Time and tape complexity measures of Turing machines; Random access machines; the classes P and NP; NP-completeness; Satisfiability and Cook's theorem; Polynomial reduction and some NP-complete problems.

Learning Outcomes:

We will be working on the top five levels of Bloom's Taxonomy.
The student will be able to (in other words, this is what the exams will test):
  • Model, compare and analyse different computational methods using combinatorial methods.
  • Apply rigorously formal mathematical methods to prove properties of languages, grammars and automata.
  • Construct algorithms for different problems and argue formally about correctness on different restricted machine models of computation.
  • Identify limitations of some computational models and possible methods of proving them.

Course Pre-requisites:

The IITM curriculum aims this core course to be delivered to the second year B.Tech students. There is no formal pre-requisite for crediting this course, other than eligibility to attend the 4th semester of your BTech course. The informal pre-requisite is CS2100: Discrete Mathematics Course.

Evaluation:

The final score will depend on four parameters:
  • Short Tests (10%) - We will be having in-class, evaluated Tutorials.
  • Quiz-I (25%) - Feb 15, 2012, 8am - 8:50am
  • Quiz-II (25%) - Mar 21, 2012, 8am - 8:50am
  • Endsem Exam (40%) - Apr 27, 2012, 9am - 12pm