|
Dr. Lalatendu Behera
Vision and Mission of the Department and Institute
Instructor
Class Timings and Venue
Wednesday: 8:30 AM - 9:25 AM
Thursday: 9:30 AM - 10:25 AM
Friday: 10:30 AM - 11:25 AM
Venue: Seminar Hall (CS 303)
Tutorial Timings and Venue
Monday: 1:30 PM - 2:25 PM (G2)
Monday: 4:30 PM - 5:25 PM (G3)
Thursday: 1:30 PM - 2:25 PM (G1)
Venue: CS 208
Course Outcomes
| CO | |
| 1 | Understand theoretical foundations of computer science. |
| 2 | Master regular languages, finite automata, pushdown automata, Turing recognizable Languages. |
| 3 | Employ finite stated machines to solve problems in computing. |
| 4 | Think analytically and intuitively for problem-solving situations in related areas of theory in computer science. |
|
|
CO - PO Mapping
| CO | PO1 | PO2 | PO3 | PO4 | PO5 | PO6 | PO7 | PO8 | PO9 | PO10 | PO11 | PO12 |
| CO1 | H | | M | | | | | | | | | |
| CO2 | M | | | H | | | M | | | | | |
| CO3 | M | | H | H | M | | M | | M | | | |
| CO4 | M | | M | H | | | M | | M | | | |
|
|
Recommended Books
J. E. Hopcroft and J. D. Ullman, “Introduction to Automata Theory, Languages and Computation”, Narosa
Publishers 2002.
Harry R. Lewis and Chritos H. Papadimitriou, “Elements of the Theory of Computation”, Pearson
Education 2001.
Michael Sipser, “Introduction to the theory of computation”, Cengage Learning, New Delhi
Classes
| Lecture No. | Date | Topic | Source |
| 1 | 27/07 | Introduction | |
| 2 | 03/08 | DFA | 1 |
| 3 | 04/08 | Examples of DFA | 1,3 |
| 4 | 05/08 | DFA and a set of strings | 1,3 |
| 5 | 16/08 | Non-determinism | 1 |
| 6 | 17/08 | NFA | 1,3 |
| 7 | 18/08 | Equivalence NFA and DFA | 1,3 |
| 8 | 24/08 | Epsilon-NFA | 1,3 |
| 9 | 25/08 | Mealy and Moore Machine | 1,3 |
| 10 | 26/08 | Equivalence of Mealy and Moore Machine | 1 |
| 11 | 31/08 | Revision | |
| 12 | 1/09 | Minor - 1 | Examination |
| 13 | 5/09 | Minor - 1 Q/A discussion | |
| 14 | 7/09 | DFA Minimization | 1,3 |
| 15 | 8/09 | Introduction to grammar and languages | 1,3 |
| 16 | 14/09 | Regular Expressions | 1,3 |
| 17 | 15/09 | Regular Expressions to Epsilon NFA | 1,3 |
| 18 | 16/09 | Regular Expressions to Epsilon NFA with examples | 1,3 |
| 19 | 21/09 | DFA to Regular Expressions with examples | 1,3 |
| 20 | 22/09 | Properties of Regular Languages | 1,3 |
| 21 | 23/09 | Pumping Lemma for Regular Languages | 1,3 |
| 22 | 28/09 | Examples of Non-regular Languages, Emptiness and Infiniteness | 1,3 |
| 23 | 29/09 | Introduction to Context-Free Grammar | 1,3 |
| 24 | 30/09 | Examples of CFG, Parse Tree | 1,3 |
| 25 | 05/10 | Ambiguous Grammar and removal of ambiguity | 1,3 |
| 26 | 06/10 | Removal of Useless Symbols and Unit Productions | 1,3 |
| 27 | 07/10 | Removal of epsilon Productions and Chomsky Normal Form | 1,3 |
| 28 | 12/10 | Revision | |
| 29 | 2/11 | Greibach Normal Form | 1,3 |
| 30 | 3/11 | Introduction to Pushdown Automata | 1,3 |
| 31 | 4/11 | Examples of Pushdown Automata | 1,3 |
| 32 | 9/11 | CFG to PDA | 1,3 |
| 33 | 10/11 | PDA to CFG | 1,3 |
| 34 | 11/11 | Pumping Lemma of CFG | 1,3 |
| 35 | 16/11 | Introduction to Turing Machine | 1,3 |
| 36 | 17/11 | Examples of Turing Machine | 1,3 |
| 37 | 18/11 | Halting Problem | 1,3 |
|
|
Homeworks
|