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)
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
Introduction to the Theory of Computation, M. Sipser
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.