CS2200 Languages, Machines, and Computation

Jan - May 2024

about

Coordinates

• Where: CS15
• When: B slot - Mon (9 am), Tue (8 am), Wed (1 pm), Fri (11 am)

Instructor

• Yadu Vasudev
• SSB 207
• yadu@cse.iitm.ac.in

TAs

• Akash (cs22d012@smail)
• Balakrishnan (cs20b012@smail)
• Bhabya (cs21d200@smail)
• Kumaresan (cs21b045@smail)
• Nagashri (cs21d004@smail)
• Narayana (cs22s004@smail)
• Sampriti (cs18d200@smail)
• Subramanian (cs23m067@smail)
• Tahir (cs20b078@smail)
• Vishnu (cs23m073@smail)

Important links

• Moodle (for problem sets)
• Ed Discussions (for discussions, Q/A, announcements)
  Join using your smail/iitm ids via this link
• Anonymous course feedback

contents

About this course

This course provides an introduction to the mathematical theory of computation. The course gives a preliminary exposure to theoretical computer science, and the formal relationships among machines and computational problems with the aim of understanding the nature of computation and its inherent limits.

Prerequisites - A basic course in discrete mathematics (CS1200 or equivalent) is a useful prerequisite for the course. This course is mathematical in nature, and will involve formal reasoning and writing proofs which is typically covered in CS1200.

---

Course contents

The following is a brief overview of the topics that will be covered in this course. The order of the topics covered may vary.

• Finite-State Machines and Regular Languages: Languages vs Computational problems, Deterministic and non-deterministic finite state automata, regular languages, closure properties, limitations - pumping lemma and Myhill-Nerode relations, state minimization, equivalent models, algorithmic questions.
• Context-Free Grammars: Grammars, Chomsky hierarchy, normal forms, closure properties, limitations - pumping lemma, algorithmic questions - parsing algorithm, equivalent models - push-down automata.
• Computability Theory - Turing machines, equivalence between different variants, Universal Turing machine, recursively enumerable and recursive sets of languages, Decidability - Halting Problem, Church-Turing thesis.
• Basic Complexity Theory - Measures of complexity, complexity classes P and NP, notion of polynomial-time reducibility, NP-completeness, satisfiability and the statement of Cook’s theorem.

---

Course resources

There are many textbooks and resources (both offline and online) that cover most of the material presented in the list above. We will not be following one textbook. Our main sources of reference will be the following textbooks.

• [K]: Automata and Computability - Dexter C. Kozen
• [HMU]: Introduction to Automata Theory, Languages and Computation - Hopcroft, Motwani and Ullman, 3rd Edition
• [S]: Introduction to the Theory of Computation - Michael Sipser, 3rd Edition

All these books contain a number of exercise problems for practice.

administrivia

Weekly schedule

There are three lectures per week and a tutorial. The tutorials are scheduled based on the amount of material covered in the lectures, and are ungraded. The tentative dates of the quizzes, tests, and tutorials are given below. We will try to stick to this schedule as much as possible.

---

Grading policy (tentative)

The course will be evaluated through a series of quizzes and finally the end-sem. I will be releasing problem sets on a weekly basis, and we will have tutorial sessions to discuss the these problems and possible approaches to solving them. The tentative grading scheme is as follows.

Grading pattern

• Class tests: 3*10 = 30% (best 3/4)
• Quiz 1 & 2: 2 * 15 = 30%
• End-sem: 40%

---

Important dates (tentative)

Please note the following dates for the ungraded tutorials and class tests. The dates for Quiz 1,2 and end-semester examination will be as per the institute calendar.

Dates

Tutorials	Jan 24, Feb 02, Feb 16, Mar 01, Mar 15, Mar 27, Apr 05, Apr 19, Apr 26
Class tests	Feb 09, Mar 06, Apr 12 16 , May 03 01
Quiz 1	Feb 20
Quiz 2	Mar 19
End-sem	May 07

---

Communication

Please sign up on the course discussion forum here. This will be the first point of contact for any issues related to the course. For general questions related to the course (any comments/doubts), please create a thread in the correct category and add your question/comment there. You are encouraged to reply and clear the doubts of your friends. To encourage this interaction, the forum supports anonymous posts and answers. Please be courteous to others when you are posting anonymously.

lectures