Instructors

Course Timings

Teaching Assistants

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.

Syllabus and Coverage

Topic	Details
Introduction	The Scientific Foundations of Computing. Proof Techniques and Fundamentals.
Logic	Propositional Logic, Satisfiabiliy and Validity. Predicate Logic, Encoding and Deduction. Resolution and Refutation Principles. Notions of Soundness and Completeness. Applications of Logic.
Discrete Structures	Set, Relation and Function. Equivalence Relation, Partition, Poset, Lattice, Morphism. Set Sizes, Countability and Uncountability, Unsolvability. Algebraic Structures and Boolean Algebra.
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.
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.
Computability	Decidability, Undecidability. Universal Machines, Halting Problem and diagonalisation. Undecidable problems, Many-One Reductions, Rice's Theorem.
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.
Conclusion	Overall Summary and The Road Ahead.

Announcements