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		[ Online Class Sessions ] MS-Teams Meeting-Link :   Monday (10:00–11:00)   |   Wednesday (08:00–10:00)   |   Thursday (10:00–11:00) [ Online Examinations ] CSE-Moodle Page-Link :   Course Page
Teaching Assistants		Kirti Agarwal, Manasvi Sagarkar, Ravi Pratap Singh, Sandeep Kumar Shahu

Notices and Announcements

August 08, 2021

We shall consider requests via ERP from BTech/Dual students till 8:00pm, 08-Aug-2021 and finalize the approval of few more among those requested students based on their CGPA (only) immediately after 8:00pm. 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 subject registration deadline is on 09-Aug-2021, the declined students are requested to switch over to other courses.
We shall NOT consider any further request for approval.

August 03, 2021

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

Syllabus and Coverage

Topic	Details	Instructor	Date	Scribes	Materials/ References
Introduction	The Scientific Foundations of Computing. Proof Techniques and Fundamentals.	Aritra Hazra	11-Aug-2021	Scribe-01a Scribe-01b	Grimaldi [1]
Logic	Propositional Logic, Satisfiabiliy and Validity. Predicate Logic and Deduction. Resolution and Refutation Principles. Notions of Soundness and Completeness.	Aritra Hazra	12-Aug-2021 16-Aug-2021 19-Aug-2021	Scribe-02a Scribe-02b Scribe-02c	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	25-Aug-2021 26-Aug-2021 01-Sep-2021 02-Sep-2021	Scribe-03a Scribe-03b Scribe-03c Scribe-03d	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	09-Sep-2021 13-Sep-2021 15-Sep-2021 20-Sep-2021 22-Sep-2021	Scribe-04a Scribe-04b Scribe-04c Scribe-04d Scribe-04e	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	27-Sep-2021 29-Sep-2021 30-Sep-2021	Scribe-05a Scribe-05b Scribe-05c	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	07-Oct-2021 11-Oct-2021 18-Oct-2021 20-Oct-2021	Scribe-06a Scribe-06b Scribe-06c Scribe-06d	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	21-Oct-2021 26-Oct-2021 27-Oct-2021 28-Oct-2021 01-Nov-2021 03-Nov-2021 08-Nov-2021 10-Nov-2021	Scribe-07a Scribe-07b Scribe-07c Scribe-07d Scribe-08a Scribe-08b Scribe-08c Scribe-08d	Sipser [4] Hopcoft-Ullman [5] Papadimitriou [9]
Conclusion	Overall Summary and The Road Ahead.	Somindu Chaya Ramanna	11-Nov-2021	–	Savage [10]

Books and References

1. Ralph P Grimaldi; Discrete and Combinatorial Mathematics; 5th Edition, Pearson Education, 2004.
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  (23-Aug-2021)  [Scribe]  (Topic: Logic)
• Tutorial-2  (30-Aug-2021)  [Scribe]  (Topic: Set, Relation, Function)
• Tutorial-3  (06-Sep-2021)  [Scribe]  (Topic: Countability and Algebraic Structures)
• Tutorial-4  (16-Sep-2021)  [Scribe]  (Topic: Finite State Automata and Regular Languages)
• Tutorial-5  (23-Sep-2021)  [Scribe]  (Topic: Push-down Automata and Context-free Languages)
• Tutorial-6  (04-Oct-2021)  [Solution]  (Topic: Turing Machines)
• Tutorial-7  (20-Oct-2021)  [Scribe | Solution]  (Topic: Recursive and Recursively Enumerable Languages, Decidability/Undecidability)
• Tutorial-8  (28-Oct-2021)  [Scribe | Solution]  (Topic: Time Complexity)
• Tutorial-9  (10-Nov-2021)  [Scribe | Solution](Topic: Space Complexity)

Assignments

• Assignment-1  (08-Sep-2021 – 17-Sep-2021)  [ Code-Template ]  [ Solution  | TestCases ]
• Assignment-2  (01-Nov-2021 – 09-Nov-2021)  [ Solution ]

Tests

• Test-1  [ Questions | Solutions ]  (08-Sep-2021, Wednesday)  [ Syllabus: Proof Techniques, Logic and Discrete Structures ]
• Test-2  [ Questions | Solutions ]  (06-Oct-2021, Wednesday)  [ Syllabus: Automata Theory and Turing Machines ]
• Test-3  [ Questions | Solutions ]  (17-Nov-2021, Wednesday)  [ Syllabus: Computability and Computational Complexity ]