Program Overview

Program Overview

The CS60005 program, Foundations of Computing Science, is offered in the Autumn 2022 semester with a lecture-tutorial-practical (L-T-P) format of 3-1-0.

Schedule

Instructors

• Somindu Chaya Ramanna
• Aritra Hazra

Timings

• Monday: 10:0011:00
• Wednesday: 08:0010:00
• Thursday: 10:0011:00

Venue

• NC341 (Nalanda Complex)

Teaching Assistants

• Burgula Pavani
• Chandratreya Vishal Pankaj
• Danny Jeron Pereira
• Shubham Kumar Das
• Srijeeta Maity

Syllabus and Coverage

Topics

• Introduction: The Scientific Foundations of Computing, Proof Techniques and Fundamentals
• Logic: Propositional Logic, Satisfiability and Validity, Predicate Logic and Deduction, Resolution and Refutation Principles, Notions of Soundness and Completeness
• 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, 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

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, Topic: Recursive and Recursively Enumerable Languages, Decidability/Undecidability
• Tutorial-8: 03-Nov-2022, Topic: Time Complexity
• Tutorial-9: 10-Nov-2022, Topic: Space Complexity

Examinations

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