CS201: Theory of Computation (July -- Nov 2017)

Welcome! This is an undergraduate course. The course (that we will cover) is mainly influenced by the two text books: (I) Introduction to the Theory of Computation, by M. Sipser and (II) Introduction to Automata Theory, Languages and Computations, by J. Hopcropt, R. Motwani, J. D. Ullman

News:

* Second quiz schedule: 07-November (Tuesday), 18:30 - 19:30, Classroom - LH2

* Mid-Sem exam schedule: 23-Sept (Saturday), 10:00 - 12:00, room - LH4

* First quiz on 07-September

* The classroom has changed to LH3

* No tutorial this week (03-August)

* Extra class on Wednesday 02-August

* First class is on 01-August 2017 (Tuesday)

Course Information

Instructor: Anisur Rahaman Molla

Office: SMS 312

Email: my_lastname at niser.ac.in

Schedule and Venue: Monday: 18:30 - 20:00 (Lecture)

Tuesday: 18:30 - 20:00 (Lecture)

Thursday: 18:30 - 19:30 (Tutorial)

Classroom: LH3

Course Description:

This a core topic of computer science. The course will introduce formal mathematical models of computation that reflect computers. Over the course we will try to find out the answer of the following questions. What is computation? Can we have a rigorous mathematical definition of computation? What are the limitations and capabilities of computers-- Can anything be computed? We will see what can be computed and how efficiently, as well as what cannot.

Course Contents:

  • Preliminaries (review of basic mathematical concepts)

  • Automata (DFA, NFA, their equivalence, regular expression, pushdown automata)

  • Language theory (regular languages, context free languages and grammars, Chomsky normal form, pumping lemma)

  • Turing machine

  • Decidability and reducibility

  • Complexity theory (notions of P, NP, co-NP, NP-Completeness)

Course Objectives:

On successful completion of the course students will be able to:

  • Understand the importance of automata as a modelling tool of computational problems

  • Understand the basis of theory of computation. The theory simplifies the complex computers to an abstract and simple mathematical model, and helps you to understand them better.

  • Understand the capabilities and limitations of computational systems

  • Learn problem solving skills: how to think, prove, argue, solve problems, express, and abstract.

Prerequisite:

None! (basic mathematical maturity is expected)

Grading Plan:

  • Quiz — 30%

  • Exams — 70% (Mid term 30%, Final 40%)

References:

Text Books

    1. Introduction to the Theory of Computation, M. Sipser

    2. Introduction to Automata Theory, Languages and Computations, J. Hopcropt, R. Motwani, J. D. Ullman

Lecture Notes

  • I will try to prepare lecture slides and/or notes (but no promise!)

Assignment: (will upload assignments here)

Caution: the page is under construction! I would be happy to have your comments.