Foundations of Computing Science

CS60005, Autumn 2023, LTP: 3-1-0

Notices and Announcements

• Class Test 2 to be held on 6 November from 5:45 PM to 6:45 PM in CSE 107, 119, 120. Room allocation can be found here.
• Mid-Sem answer scripts will be shown on 2nd November from 6 PM to 7 PM. Venue will be notified soon. Students are advised to go through the solutions carefully before coming to see the scripts.
• Class Test 1 to be held on 4 September 2023 from 6:15 PM to 7:15 PM at CSE 107,108,119,120. Room allocation to be shared by email.
• I will consider requests via ERP from BTech/Dual students until 6 PM on 7th August. Final approval will be based on CGPA and the year of joining the institute. Since this is an M.Tech. (CS) core course, I cannot approve all requests.
• First class is on the 2nd of August, 2023 at 8 AM.

Syllabus

• Introduction

  • Introduction to Foundations of Computing
  • Proof Techniques

• Logic (Ref: 1,2,3)

  • Propositional Logic: Statements, Connectives, Satisfiabiliy and Validity, Deduction Rules, Equivalences.
  • Predicate Logic: Quantification, Proof Theory and Equivalences.
  • Soundness and Completeness.

• Discrete Structures (Ref: 1,2)

  • Sets, Relations and Functions.
  • Equivalence Relation, Partition, Posets.
  • Set Cardinality, (Un)Countability.
  • Algebraic Structures.

• Languages and Automata Theory (Ref: 4,6)

  • Strings and Languages
  • Finite Automata (DFA and NFA) and Regular Languages.
  • Properties of Regular Languages, Pumping Lemma for Regular Languages.
  • Push-down Automata and Context-free Languages, Context-Free/Type-2 Grammars.
  • Operations on Languages, Closures with respect to the Operations.

• Turing Machines (Ref: 4,6)

  • Modelling Effective Computation, Turing Machines, Church-Turing thesis.
  • Turing Machine Construction, Variants of Turing machines and equivalence.
  • Properties of Recursive and Recursively Enumerable Languages.

• Computability (Ref: 4)

  • Decidability, Undecidability.
  • Universal Machines, Halting Problem and diagonalisation.
  • Undecidable problems, Many-One Reductions, Rice's Theorem.

• Computational Complexity (Ref: 7)

  • 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.

References

1. Discrete and Combinatorial Mathematics by Ralph P Grimaldi, Pearson Education, 2006.


2. Discrete Mathematical Structures with Applications to Computer Science by Jean-Paul Tremblay and R Manohar, 1st Edition, Tata McGraw-Hill Education, 2017.


3. Logic in Computer Science – Modelling and Reasoning about Systems by Michael Huth and Mark Ryan, 2nd Edition, Cambridge University Press, 2004.


4. Automata and Computability by Dexter Kozen.


5. Computational Complexity by S. Arora and B. Barak.


6. Introduction to Automata Theory, Languages and Computation by John E. Hopcroft and Jeffrey D. Ullman.


7. Introduction to the Theory of Computation by Michael Sipser.


8. Elements of the Theory of Computation by H. Lewis and C. Papadimitriou.


9. Computational Complexity by C. H. Papadimitriou.


10. Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson.


11. Models of Computation – Exploring the Power of Computing by John E. Savage, Pearson Education, 1997.

Evaluation Plan (Tentative)

• 2 Tests (20% of total credit)
• Mid Semester Examination (30% of total credit)
• End Semester Examination (50% of total credit)

Tutorials

Tests/Exams