CSL 705: Theory of Computation Semester II 2010-2011 Instructor : Sandeep Sen

Lectures: M,T,W : 12 - 12:50 Venue IIA 204

Tutorials: Wed 3-4pm Venue IIA 204

Office hours: M 4 -5

Teaching Assistant:

• Manoj G. (CSE Research Scholar Room, Office hrs Tue, Thu 4-5 p)

  Grading

  The total will be computed as Minors 1 and 2 - 20% each, Major 40%, Quizes and tutorial performance - 20%. Note that students having less than 75% attendence will be reported for possible penal action according to the new attendence rules of the institute.

  Prerequisites: CSL105 (Discrete Structures)

  Background Material in Discrete Structures

  Lecture outlines (including NP completeness)

  Tutorial Problems

  Problem Set 0 Solns by TA

  Problem Set 1 (TM & undecidability) Solns by TA

  Problem Set 2 (Regular Languages)

  Minor 1 Solutions

  Problem Set 3 (CFL)

  Problem Set 4

  Minor 2 Solutions

  Major exam Solutions

  Recommended : CSL201 (Data Structures)

  Contents.

  Formal Languages Regular Languages, Finite Automata, equivalence, minimization, Myhill Nerode theorem, Introduction to non-determinism, Context Free Grammars, Pushdown Automata, Equivalence and Applications

  Computability : Turing Machines, Recursive and recursively enumerable sets, RAMs and equivalence, Universal Turing Machine, Undecidability, Rices theorem for recursive and re sets, Recursive function theory and equivalence, Church Turing Thesis

  Computational Complexity : Space Time complexity, Savage's theorem, Complexity classes, Complete problems, NP completeness, Cook-Levin theorem and reductions
  
  

  Reference books

  Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman, Pub: Narosa

  Automata and Computability Kozen Pub- Springer (Indian reprint available)

  ---

  Sandeep Sen
  Last modified: Mon July 18 2006