CS 2200 : Languages, Machines and Computation

In Semester 2, 2018-2019, I will be teaching CS 2200: Languages, Machines and Computation.

Administrative Information.

When and Where.

Classes are held on Monday 9 am, Tuesday 8 am, Wednesday 1 pm and Friday 11:00 am. Location: CSB 36.

Office Hours and Teaching Assistants.

The teaching assistants for the course are listed below. Office hours to be decided.

• Rachit Garg. Email: CS14B050@smail.iitm.ac.in
• Monosij Maitra. Email: CS15D010@smail.iitm.ac.in
• Ankit Kumar Yadav. Email: CS16S039@smail.iitm.ac.in
• Shiladitya Biswas. Email: CS17M043@smail.iitm.ac.in
• Rajarshi Biswas. Email: CS17S007@smail.iitm.ac.in
• Anshu Yadav. Email: CS18D008@smail.iitm.ac.in
• Vankam Sree Hari. Email: CS17M059@smail.iitm.ac.in
• Nisha K K. Email: CS18D002@smail.iitm.ac.in
• Anoop S K M. Email: CS18D003@smail.iitm.ac.in



Pre-requisites.

This is a core course for second year B.Tech students. There is no formal pre-requisite other than eligibility to attend the 4th semester of your BTech course. The informal pre-requisite is CS2100: Discrete Mathematics.



Academic Calendar.

Below is the tutorial and exam schedule for the course.
• Tutorials: 29/01/19, 06/02/19, 08/02/19, 13/02/19, 22/02/19, 06/03/19, 18/03/19, 20/03/19, 03/04/19, 10/04/19, 23/04/19.
• Short Exams: 08/02/19, 06/03/19, 20/03/19, 23/04/19.
• Minor and Major exams: 19/02/19, 26/03/19 and 30/04/19.



Office Hours.

Instructor office hours are W-F 2-3 pm in BSB 347.
TA Office hours:

• Rachit: Thursday 3:30-4:30 pm.
• Monosij: Friday, 4.30 -5.30 pm.
• Ankit: Friday, 4.00 -5.00 pm.
• Shiladitya: Wednesday 4:00 -5:00 pm.
• Sree Hari: Thursday 5:00 -6:00 pm.
• Rajarshi: Friday 4:30 - 5:30 pm.
• Nisha: Thursday 4:00 - 5:00 pm.
• Anoop: Thursday 4:00 -5:00 pm.
• Anshu: Wednesday 3:00 -4:00 pm.



Course Description.

The objective of the course is to introduce students to the foundations of computation. We ask fundamental questions like "What does it mean for a function to be computed?", "Are all functions computable?", "Is there a way to measure the hardness of computing a function?" We will see that the above questions are deep, and in the quest for answering them we will learn some fundamental concepts such as state, transition, reduction, decidability.



Textbooks and References.

The textbooks for the course are Michael Sipser's "Introduction to the Theory of Computation" and "Automata and Computability" by Dexter Kozen. The library should have multiple copies. Slides used in last class are here. I also found some very nice slides here.



Syllabus

The topics are broadly categorized as follows.

• Finite Automata & Regular Languages (Ch 1 of Sipser, Ch 13-16 of Kozen):Introduction to automata theory, languages and computational problems. Finite state automata, Regular Languages. Deterministic and Non-deterministic finite automata, Subset construction. Regular Expressions, Pattern Matching, pumping lemma, DFA state minimization, Myhill Nerode relations, Myhill Nerode theorem.


• Context Free Languages and Push Down Automata (Ch 2 of Sipser and Ch 20 and 27 of Kozen) :Context free grammars - Derivation trees and ambiguity -Chomsky normal form - Pushdown automata - Acceptance by empty store and final state - Equivalence between push-down automata and context-free grammars - Pumping lemma - PAREN language and its grammar - CYK algorithm - Closure properties of CFL.
  
  
• Turing machines & Computability (Ch 3, 4 and 5 of Sipser): Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Universal Turing machine - Turing recognizable and decidable - linear bounded automata. Decidability; Post's correspondence problem; Rice's theorem; decidability of membership, emptiness and equivalence problems of languages, reductions.
  




Requirements.

• 2 Quizzes: 20% each.
• Final Exam: 40%.
• Tutorials: 20% distributed over 4 short exams 5% each.



Policies and Grades.

Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help you in solving some problems, you should mention the source in your writeup. Class participation will also be taken into account when assigning grades.
I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class plus being sent to the disciplinary committee. Read about plagiarism here.