Schedule

Instructors		Somindu Chaya Ramanna   and   Aritra Hazra
Timings		Monday (10:00–11:00), Wednesday (08:00–10:00), Thursday (10:00–11:00)
Venue		NC341 (Nalanda Complex)
Teaching Assistants		Burgula Pavani | Chandratreya Vishal Pankaj | Danny Jeron Pereira | Shubham Kumar Das | Srijeeta Maity

Notices and Announcements

November 11, 2022

Syllabus for the end semester examination includes everything taught in the course. 20% of the questions will be from Pre-Midsem syllabus.
An online study session (VC link sent through email) has been arranged for those who have difficulty understanding the topics covered after midsem. It starts at 10:00 PM and ends at 12:00 AM, starting from 11-Nov-2022 to 15-Nov-2022.

August 01, 2022

The first class will be held on 03-August-2022 (Wednesday) at 8:00am.
An e-mail with all relevant details will be sent to the enrolled students before that. Stay tuned ...

July 25, 2022

We shall consider requests via ERP from BTech/Dual students till 8:00pm, 01-Aug-2022 and finalize the approval of few more among those requested students based on their CGPA (only) immediately after 8:00pm (if possible). Please note that, this is an M.Tech. core course from CSE, so we cannot take all requested students due to seat limitation. Considering the first class to be held on 03-Aug-2022, the declined students are requested to switch over to other courses before the subject registration deadline expires. We shall NOT consider any further request for approval beyond that.

Syllabus and Coverage

Topic	Details	Instructor	Date	References
Introduction	The Scientific Foundations of Computing. Proof Techniques and Fundamentals.	Aritra Hazra	03-Aug-2022	Grimaldi [1]
Logic	Propositional Logic, Satisfiabiliy and Validity. Predicate Logic and Deduction. Resolution and Refutation Principles. Notions of Soundness and Completeness.	Aritra Hazra	04-Aug-2022 08-Aug-2022 10-Aug-2022	Grimaldi [1] Huth-Ryan [3]
Discrete Structures	Set, Relation and Function. Equivalence Relation, Partition, Poset, Lattice, Morphism. Set Sizes, Countability and Uncountability, Unsolvability. Algebraic Structures and Boolean Algebra.	Aritra Hazra	10-Aug-2022 17-Aug-2022 24-Aug-2022 25-Aug-2022	Grimaldi [1] Tremblay-Manohar [2]
Languages & Automata Theory	Chomsky Hierarchy of Grammars and the Corresponding Acceptors. Finite Automata (DFA and NFA) and Regular Languages. Non-regular Languages and Pumping Lemma. Push-down Automata and Context-free Languages, Grammers. Operations on Languages, Closures with respect to the Operations.	Aritra Hazra + Somindu Chaya Ramanna	31-Aug-2022 01-Sep-2022 07-Sep-2022 08-Sep-2022 12-Sep-2022	Hopcoft-Ullman [5] Kozen [6] Sipser [4] Lewis-Papadimitriou [8]
Turing Machines	Turing Machines, Church-Turing thesis. Turing Machine Construction, Variants of Turing machines and equivalence. Properties of Recursive and Recursively Enumerable Languages.	Somindu Chaya Ramanna	15-Sep-2022 10-Oct-2022 12-Oct-2022	Kozen [6,7] Hopcoft-Ullman [5] Sipser [4] Lewis-Papadimitriou [8]
Computability	Decidability, Undecidability. Universal Machines, Halting Problem and diagonalisation. Undecidable problems, Many-One Reductions, Rice's Theorem.	Somindu Chaya Ramanna	17-Oct-2022 19-Oct-2022 24-Oct-2022 26-Oct-2022	Kozen [6,7] Hopcoft-Ullman [5] Sipser [4] Lewis-Papadimitriou [8]
Computational Complexity	Notion of Time Complexity and Measuring Complexity. The Classes P, NP, Co-NP and NP-Completeness. Problem Reduction, Polynomial Hierarchy and Hierarchy Theorem. Space Complexity and Savich's Theorem. The Classes PSPACE, PSPACE-Complete, L, NL, Co-NL. Problem Reduction and Log-Space Reducibility, NL-Completeness.	Somindu Chaya Ramanna	27-Oct-2022 31-Oct-2022 02-Nov-2022 07-Nov-2022 08-Nov-2022	Sipser [4] Hopcoft-Ullman [5] Papadimitriou [9]
Conclusion	Overall Summary and The Road Ahead.	Somindu Chaya Ramanna	14-Nov-2022	Savage [10]

Books and References

1. Ralph P Grimaldi; Discrete and Combinatorial Mathematics; Pearson Education, 2006.
2. Jean-Paul Tremblay and R Manohar; Discrete Mathematical Structures with Applications to Computer Science; 1st Edition, Tata McGraw-Hill Education, 2017.
3. Michael Huth and Mark Ryan; Logic in Computer Science – Modelling and Reasoning about Systems; 2nd Edition, Cambridge University Press, 2004.
4. Michael Sipser; Introduction to the Theory of Computation; 3rd Edition, Cengage Publishers, 2014.
5. John E. Hopcroft and Jeffrey D. Ullman; Introduction to Automata Theory, Languages, and Computation; 1st Edition, Addison-Wesley, 1979.
6. Dexter Kozen; Automata and Computability; Springer, 1997.
7. Dexter Kozen; Theory of Computation; Springer, 2006.
8. Harry Lewis and Christos Papadimitriou; Elements of the Theory of Computation; 2nd Edition, Pearson Education, 1997.
9. Christos Papadimitriou; Computational Complexity; 1st Edition, Pearson Education, 1994.
10. John E. Savage; Models of Computation – Exploring the Power of Computing; Pearson Education, 1997.

Tutorials

• Tutorial-1  [11-Aug-2022]  (Topic: Logic)
• Tutorial-2  [22-Aug-2022]  (Topic: Set, Relation, Function)
• Tutorial-3  [29-Aug-2022]  (Topic: Countability and Algebraic Structures)
• Tutorial-4  [05-Sep-2022]  (Topic: Finite State Automata and Regular Languages)
• Tutorial-5  [14-Sep-2022]  (Topic: Push-down Automata and Context-free Languages)
• Tutorial-6  (13-Oct-2022)  (Topic: Turing Machines)
• Tutorial-7  (20-Oct-2022)  [Solution]  (Topic: Recursive and Recursively Enumerable Languages, Decidability/Undecidability)
• Tutorial-8  (03-Nov-2022)  [Solution]  (Topic: Time Complexity)
• Tutorial-9  (10-Nov-2022)  [Solution]  (Topic: Space Complexity)

Examinations

• Class Test 1  [ Questions | Solutions ]  (01-Sep-2022, Thursday, 17:30-18:30)  [ Syllabus: Proof Techniques, Logic and Discrete Structures ]
• Mid-Semester  [ Questions | Solutions ]  (22-Sep-2022, Thursday, 09:00-11:00)  [ Syllabus: till Languages and Automata Theory ]
• Class Test 2  [ Questions | Solutions ]  (05-Nov-2022, Saturday, 10:30-11:30)  [ Syllabus: Turing Machines and Computability ]
• End-Semester  [ Questions | Solutions ]  (18-Nov-2022, Friday, 14:00-17:00)  [ Syllabus: Full ]