CS 637 Mathematics II: Theory of Computation and Graph Theory, Spring 2024

Instructor: Prof. Neminath Hubballi (neminath@iiti.ac.in), Department of Computer Science and Engineering, IIT Indore
Teaching Assistants: Nisha Kumari Barsha (ms2204101007@iiti.ac.in) and Suhas Hegde (ms2304101013@iiti.ac.in)

This is an advanced level course designed to provide theoretical background of Computer Science to the students. It explores the theoretical limits of computation and provides necessary ingredients to show what can be computed. It also covers some important topics in graph theory.

Classroom:

C01 - Lecture Hall Complex

Course Delivery:

2 Lectures and 1 Tutorial per week. We will use blackboard to the extent possible. Occasionally, we might use slides to cover some topics (blackboard is too small in this classroom!). Tutorials will involve problem solving on the topics discussed during the lectures.

Lecture Schedule

Week Topic Reading/Reference Material
Week 1 Basics of Theory of Computation, Language, Standard Turing Machine 7.1 – 7.2 of Textbook-2
Week 2 Computable Functions, Turing Machine as Language Acceptor and Transducer. 7.3 of Textbook-2

Text Books:

  1. Kenneth H. Rosen, Kamala Krithivasan, “Discrete mathematics and Its Applications (SIE)", 8th Edition, McGraw Hill, 2021
  2. John E.Hopcroft , Jeffrey D.Ullman, “Introduction to Automata Theory Languages And Computation”, Rainbow Book Distributors, 2008
  3. Sanjeev Arora and Boaz Barak “Computational Complexity: A Modern Approach”, Cambridge University Press, 2009