E0 222 Formal Methods in Computer Science

• Course outline

  The course will essentially be a course on Theory of Computation.

  • Automata Theory & Computability:
    • Finite automata and their use in modelling,
    • pushdown automata,
    • context free languages,
    • Turing machines,
    • undecidability.
  • Complexity Theory:
    • Basic complexity classes,
    • reductions, hardness and completeness with emphasis on NP-completeness.

• Books and other material
  1. Hopcroft J.E. and Ullman, J.D.: Introduction to Automata, Languages and Computation. Addison Wesley, 1979.
  2. Dexter Kozen: Automata and Computability. Springer, 1999.
  3. H. R. Lewis and C. H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1981.
  4. C. H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994.

• Assignments (to be put up; there will 6-8 assignments during the course)
  • Assignment 1.
    Solutions for Assignment 1.
  • Assignment 2.
    Perl Script todot.pl.
    
  • Assignment 3.
    
  • Assignment 4.
    
  • Assignment 5.
    
  • Assignment 6.
    

• Seminar Topics (meeting on Friday's at 11:30am).
  • Collapsing NFA states (S. Rahul: 26 Sept)
  • Ultimate periodicity and regularity preserving functions (Mangesh Gupte: 3:30pm Fri, 10 Oct)
  • Term automata
  • Logical characterisation of regular languages (Deepak Bharadwaj, Monu Agarwal: 11:30 am Fri, 17 Oct)
  • The Chomsky-Schutzenberger theorem (Sivaram Prasad, 20 Oct)
  • two-way DFA's
  • CKY parsing algorithm (A. Indra, Fri 31 Oct).
  • Deterministic PDA's (Ravi Chandra Kondamuru, Fri 7 Nov).
  • Efficient Regular Expression search (Pradeep Chauhan, Krishna Kumar, Fri 14 Nov).
  • 2-DFA's (Archana R, Rajani Pai, Fri 14 Nov).
  • Mu-recursive functions capture Turing computable functions (Shijesta Victor, Shreejith Menon)
  • On Saturday 22 Nov, 10:00 am:
    • Grammars and computability (Venkata Ramayya, Jayadev C)
    • Efficient algorithm for DFA minimization (K. Shyam)
    • Context Sensitive Grammars and Linear Bounded Automata (Deepak Patil, L. Ravi).
    • Undecidability of Post Correspondence Problem and Tiling Problem (Mythri A, Amarnath Mullick)

• Proposed weightage for evaluation:
  • Mid-semester Exam: 20%
  • Assignments (Lab + written) + Seminar: 40%
  • Final Exam: 40%

• Current meeting schedule: Mon & Wed 11:30 am, in CSA Seminar Room.

• Exam Schedule:
  • Mid-semester Exam: 10:00 am, Sat, 11 Oct 2003.
  • Final Exam: Mon, 08 Dec 2003 at 9:30am.