Schedule

Instructor		Aritra Hazra
Timings [Slot: C4]		Monday (10:00–11:00), Wednesday (08:00–10:00), Thursday (10:00–11:00)
Venue		NC-141 (Nalanda Complex)
Teaching Assistants		Bibek Pal   |   Sourav Das   |   Sunandan Adhikary

Notices and Announcements

November 21, 2024

The evaluated answer scripts of end-semester examination will be shown on 26-Nov-2024 (Tuesday) at 6:00pm in CSE-107 (Ground Floor, CSE Dept.)

November 08, 2024

The evaluated answer scripts of first class test will be shown on 11-Nov-2024 (Monday) at 5:00pm in CSE-120 (Ground Floor, CSE Dept.)

November 01, 2024

The end-semester examination will be held on 20-November-2024 (Wednesday) at 9:00am (venue and seat allocations are done centrally).

October 23, 2024

The second class test will be held on 29-October-2024 (Tuesday) at 5:30pm.

September 20, 2024

The evaluated answer scripts of mid-semester examination will be shown on 26-Sept-2024 (Thursday) at 6:30pm in CSE-120 (Ground Floor, CSE Dept.)

September 11, 2024

The mid-semester examination will be held on 19-September-2024 (Thursday) at 9:00am (venue and seat allocations are done centrally).

August 29, 2024

The evaluated answer scripts of first class test will be shown on 04-Sept-2024 (Wednesday) at 5:00pm in CSE-120 (Ground Floor, CSE Dept.)

August 20, 2024

The first class test will be held on 27-August-2024 (Tuesday) at 6:00pm.

July 20, 2024

The first class will be held on 22-July-2024 (Monday) at 10:00am.
An e-mail with all relevant details will be sent to the enrolled students before that. Stay tuned ...

July 08, 2024

Please note that, this is an M.Tech./PG Core Course from CSE, and hence the course is already heavily loaded. I shall consider requests via ERP from Non-CSE BTech/Dual students till 8:00pm, 19-July-2024 and finalize the approval of a few more among those requested students after that (based on CGPA and preferring final year students). I request CSE BTech/Dual students to NOT apply in this course. I may be unable to admit all requested students due to seat limitation. Considering the first class to be held on 22-July-2024, the declined students are requested to switch over to other courses before the subject registration deadline expires. I shall NOT consider any further request for approval beyond that.

Syllabus and Coverage

Topic	Details	Date	References
Introduction	The Scientific Foundations of Computing. Proof Techniques and Fundamentals.	22-Jul-2024 24-Jul-2024	Grimaldi [1]
Logic	Propositional Logic, Satisfiabiliy and Validity. Predicate Logic, Encoding and Deduction. Resolution and Refutation Principles. Notions of Soundness and Completeness. Applications of Logic.	25-Jul-2024 29-Jul-2024 31-Jul-2024	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.	05-Aug-2024 07-Aug-2024 08-Aug-2024 14-Aug-2024 21-Aug-2024	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.	26-Aug-2024 28-Aug-2024 29-Aug-2024 04-Sep-2024 05-Sep-2024 09-Sep-2024	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. Unrestricted Grammar and Equivalence with Turing Machines. Properties of Recursive and Recursively Enumerable Languages.	12-Sep-2024 26-Sep-2024 30-Sep-2024 03-Oct-2024	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.	14-Oct-2024 16-Oct-2024 21-Oct-2024	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.	24-Oct-2024 28-Oct-2024 30-Oct-2024 04-Nov-2024 06-Nov-2024 07-Nov-2024 11-Nov-2024	Sipser [4] Hopcoft-Ullman [5] Papadimitriou [9]
Conclusion	Overall Summary and The Road Ahead.	13-Nov-2024	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

Topics	Date	Materials
Logic	01-Aug-2024	Tutorial-1
Set, Relation, Function	12-Aug-2024	Tutorial-2
Countable and Uncountable Sets	19-Aug-2024	Tutorial-3
Algebraic Structures	22-Aug-2024	Tutorial-4
Finite State Automata and Regular Languages	02-Sep-2024	Tutorial-5
Push-down Automata and Context-free Languages	11-Sep-2024	Tutorial-6
Turing Machines, Equivalent Models, and Unrestricted Grammars	14-Oct-2024	Tutorial-7
Recursive and Recursively Enumerable Languages (Un)Decidability, Reduction and Rice's Theorem	23-Oct-2024	Tutorial-8
Time Complexity	06-Nov-2024	Tutorial-9
Space Complexity	13-Nov-2024	Tutorial-10

Examinations

• Class Test 1   [ Question | Solution ]
  (27-Aug-2024, Tuesday, 6:00pm-7:00pm, Room: CSE-107+119+120, Marks: 20)
  [ Syllabus: Proof Techniques, Logic and Discrete Structures (before Algebraic Structures) ]


• Mid-Semester   [ Question | Solution ]
  (19-Sep-2024, Thursday, 09:00am-11:00am, Room: Central-Allocation, Marks: 60)
  [ Syllabus: Everything upto Languages and Automata Theory ]


• Class Test 2   [ Question | Solution ]
  (29-Oct-2024, Tuesday, 5:30pm-6:30pm, Room: CSE-107+119+120, Marks: 20)
  [ Syllabus: Turing Machines and Computability ]


• End-Semester   [ Question | Solution ]
  (20-Nov-2024, Wednesday, 09:00am-12:00pm, Room: Central-Allocation, Marks: 100)
  [ Syllabus: Everything Covered in Class ]

Marks Distribution:   20% Class-Tests + 30% Mid-Sem + 50% End-Sem  (i.e. half the marks that you receive from all the above tests)